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 subcubic algorithm then for any ϵ>0, NDTIME([ 1/2 log2 n ], n)⊈DTIME(n1+12+k-ϵ). If the APSP problem does not admit a truly subcubic algorithm already when the edge weights are of moderate size then we obtain an even stronger implication, namely that for any ϵ>0, NDTIME([ 1/2 log2 n ], n)⊈DTIME(n1.5-ϵ). Similarly, we show that if the triangle detection problem (DT) in a graph on N vertices does not admit a truly sub-Nω-time algorithm then for any ϵ>0, NDTIME([ 1/2 log2 n ], n)⊈DTIME(nw/2-ϵ), where ω stands for the exponent of fast matrix multiplication. For the more general problem of detecting a minimum weight ω>-clique (MWCω>) in a graph with edge weights of moderate size, we show that the non-existence of truly sub-Nω>-time algorithm yields for any ϵ>0, NDTIME((ω>-2)[ 12 log2n ],n)⊈DTIME(n1+ω>-22-ϵ). Next, we show that if 3SUM for N integers in { -2Nk+o(1),.2Nk+o(1) } for some k≥0, does not admit a truly subquadratic algorithm then for any ϵ>0, NDTIME([ log2n ],n)⊈DTIME(n1+11+k-ϵ). Finally, we observe that the Exponential Time Hypothesis (ETH) implies NDTIME([ k log2n ],n)⊈DTIME(n) for some k>0, while the strong ETH (SETH) yields for any ϵ>0, NDTIME([ log2n ],n)⊈DTIME(n2-ϵ). For comparison, the strongest known result on separation between non-deterministic and deterministic time only asserts NDTIME(O(n),n)⊈DTIME(n).

Ämnesord

NATURVETENSKAP  -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)

NATURAL SCIENCES  -- Computer and Information Sciences -- Computer Sciences (hsv//eng)

Nyckelord

3SUM hypothesis

APSP hypothesis

deterministic/non-deterministic time complexity

ETH conjecture

triangle detection

Publikations- och innehållstyp

art (ämneskategori)

ref (ämneskategori)