Consequences of APSP, triangle detection, and 3SUM hardness for separation between determinism and non-determinism
(2021) 11th Latin and American Algorithms, Graphs and Optimization Symposium, LAGOS 2021 In Procedia Computer Science 195. p.163-171- Abstract
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... (More)
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).
(Less)
- author
- Lingas, Andrzej LU
- organization
- publishing date
- 2021
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- 3SUM hypothesis, APSP hypothesis, deterministic/non-deterministic time complexity, ETH conjecture, triangle detection
- in
- Procedia Computer Science
- volume
- 195
- pages
- 9 pages
- publisher
- Elsevier
- conference name
- 11th Latin and American Algorithms, Graphs and Optimization Symposium, LAGOS 2021
- conference location
- Sao Paulo, Brazil
- conference dates
- 2021-05-01 - 2021-05-01
- external identifiers
-
- scopus:85122931561
- ISSN
- 1877-0509
- DOI
- 10.1016/j.procs.2021.11.022
- language
- English
- LU publication?
- yes
- id
- 99374e86-5f85-4254-a1b3-b03ff49a984d
- date added to LUP
- 2022-03-08 14:28:58
- date last changed
- 2022-04-24 05:52:37
@article{99374e86-5f85-4254-a1b3-b03ff49a984d, abstract = {{<p>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 { -2<sup>Nk+o(1)</sup>,.,2<sup>Nk+o(1)</sup>}, 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<sup>ω</sup>-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).</p>}}, author = {{Lingas, Andrzej}}, issn = {{1877-0509}}, keywords = {{3SUM hypothesis; APSP hypothesis; deterministic/non-deterministic time complexity; ETH conjecture; triangle detection}}, language = {{eng}}, pages = {{163--171}}, publisher = {{Elsevier}}, series = {{Procedia Computer Science}}, title = {{Consequences of APSP, triangle detection, and 3SUM hardness for separation between determinism and non-determinism}}, url = {{http://dx.doi.org/10.1016/j.procs.2021.11.022}}, doi = {{10.1016/j.procs.2021.11.022}}, volume = {{195}}, year = {{2021}}, }