Search: onr:"swepub:oai:lup.lub.lu.se:99374e86-5f85-4254-a1b3-b03ff49a984d" >
Consequences of APS...
Consequences of APSP, triangle detection, and 3SUM hardness for separation between determinism and non-determinism
-
- Lingas, Andrzej (author)
- Lund University,Lunds universitet,Institutionen för datavetenskap,Institutioner vid LTH,Lunds Tekniska Högskola,Department of Computer Science,Departments at LTH,Faculty of Engineering, LTH
-
(creator_code:org_t)
- Elsevier BV, 2021
- 2021
- English 9 s.
-
In: Procedia Computer Science. - : Elsevier BV. - 1877-0509. ; 195, s. 163-171
- Related links:
-
http://dx.doi.org/10... (free)
-
show more...
-
https://doi.org/10.1...
-
https://lup.lub.lu.s...
-
https://doi.org/10.1...
-
show less...
Abstract
Subject headings
Close
- 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).
Subject headings
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Keyword
- 3SUM hypothesis
- APSP hypothesis
- deterministic/non-deterministic time complexity
- ETH conjecture
- triangle detection
Publication and Content Type
- art (subject category)
- ref (subject category)
Find in a library
To the university's database