Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Consequences of APSP, triangle detection, and 3SUM hardness for separation between determinism and non-determinism

Lingas, Andrzej LU (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)
Please use this url to cite or link to this publication:
author
organization
publishing date
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 ϵ&gt;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 ϵ&gt;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 ϵ&gt;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 ω&gt;-clique (MWCω&gt;) in a graph with edge weights of moderate size, we show that the non-existence of truly sub-Nω&gt;-time algorithm yields for any ϵ&gt;0, NDTIME((ω&gt;-2)[ 12 log2n ],n)⊈DTIME(n1+ω&gt;-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 ϵ&gt;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&gt;0, while the strong ETH (SETH) yields for any ϵ&gt;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}},
}