Consequences of APSP, triangle detection, and 3SUM hardness for separation between determinism and non-determinism
Let NDTIME(f(n),g(n)) denote the class of problems solvable in O(g(n)) time by a multi-tape Turing machine using an f(n)-bit non-deterministic oracle, and let DTIME(g(n)) = NDTIME(0, g(n)). We show that if the all-pairs shortest paths problem (APSP) for directed graphs with N vertices and integer edge weights within a super-exponential range { -2Nk+o(1),.,2Nk+o(1)}, k≥1 does not admit a truly subc