Exponential time hypothesis

The {{nowrap|$k$-SAT}} problem is a version of the Boolean satisfiability problem in which the input to the problem is a Boolean expression in conjunctive normal form (that is, an and of ors of variables and their negations) with at most $k$ variables per clause. The goal is to determine whether this expression can be made to be true by some assignment of Boolean values to its variables. 2-SAT has a linear time algorithm, but all known algorithms for larger $k$ take exponential time, with the base of the exponential function depending on $k$. For instance, the WalkSAT probabilistic algorithm can solve {{nowrap|$k$-SAT}} in average time $$\backslash left(2-\backslash frac2k\backslash right)^n\; n^\{O(1)\},$$ where $n$ is the number of variables in the given {{nowrap|$k$-SAT}} {{nowrap|instance.{{r|s99}}}} For each {{nowrap|integer $k\backslash ge\; 3$,}} define $s\_k$ to be the smallest number such that {{nowrap|$k$-SAT}} can be solved in {{nowrap|time $2^\{s\_k\; n+o(n)\}$.}} This minimum might not exist, if a sequence of better and better algorithms have correspondingly smaller exponential growth in their time bounds; in that case, define $s\_k$ to be the infimum of the real numbers $\backslash delta$ for which {{nowrap|$k$-SAT}} can be solved in {{nowrap|time $O(2^\{\backslash delta\; n\})$.}} Because problems with larger $k$ cannot be easier, these numbers are ordered as {{nowrap|$s\_3\backslash le\; s\_4\backslash le\; \backslash cdots$,}} and because of WalkSAT they are at most The exponential time hypothesis is the conjecture that they are all nonzero, or equivalently, that the smallest of them, {{nowrap|$s\_3$,}} is {{nowrap|nonzero.{{r|ip99}}}}

Some sources define the exponential time hypothesis to be the slightly weaker statement that 3-SAT cannot be solved in {{nowrap|time $2^\{o(n)\}$.}} If there existed an algorithm to solve 3-SAT in {{nowrap|time $2^\{o(n)\}$,}} then $s\_3$ would equal zero. However, it is consistent with current knowledge that there could be a sequence of 3-SAT algorithms, each with running time $O(2^\{\backslash delta\_i\; n\})$ for a sequence of numbers $\backslash delta\_i$ tending towards zero, but where the descriptions of these algorithms are so quickly growing that a single algorithm could not automatically select and run the most appropriate one. If this were to be the case, then $s\_3$ would equal zero even though there would be no single algorithm running in {{nowrap|time $2^\{o(n)\}$.{{r|fg}}}} A related variant of the exponential time hypothesis is the non-uniform exponential time hypothesis, which posits that there is no family of algorithms (one for each length of the input, in the spirit of advice) that can solve 3-SAT in {{nowrap|time $2^\{o(n)\}$.{{r|cef}}}}

Because the numbers $s\_3,s\_4,\backslash dots$ form a monotonic sequence that is bounded above by one, they must converge to a limit $$s\_\backslash infty=\backslash lim\_\{k\backslash to\backslash infty\}\; s\_k.$$ The strong exponential time hypothesis (SETH) is the conjecture {{nowrap|that $s\_\backslash infty=1$.{{r|cip}}}}

It is not possible for $s\_k$ to equal $s\_\backslash infty$ for any {{nowrap|finite $k$:}} as {{harvtxt|Impagliazzo|Paturi|Zane|2001}} showed, there exists a constant $\backslash alpha$ such {{nowrap|that $s\_k\backslash le\; s\_\backslash infty(1-\backslash alpha/k)$.}} Therefore, if the exponential time hypothesis is true, there must be infinitely many values of $k$ for which $s\_k$ differs {{nowrap|from $s\_\{k+1\}$.{{r|ipz01}}}}

An important tool in this area is the sparsification lemma of {{harvtxt|Impagliazzo|Paturi|Zane|2001}}, which shows that, for {{nowrap|every $\backslash varepsilon>0$,}} any {{nowrap|$k$-CNF}} formula can be replaced by $O(2^\{\backslash varepsilon\; n\})$ simpler {{nowrap|$k$-CNF}} formulas in which each variable appears only a constant number of times, and therefore in which the number of clauses is linear. The sparsification lemma is proven by repeatedly finding large sets of clauses that have a nonempty common intersection in a given formula, and replacing the formula by two simpler formulas, one of which has each of these clauses replaced by their common intersection and the other of which has the intersection removed from each clause. By applying the sparsification lemma and then using new variables to split the clauses, one may then obtain a set of $O(2^\{\backslash varepsilon\; n\})$ 3-CNF formulas, each with a linear number of variables, such that the original {{nowrap|$k$-CNF}} formula is satisfiable if and only if at least one of these 3-CNF formulas is satisfiable. Therefore, if 3-SAT could be solved in subexponential time, one could use this reduction to solve {{nowrap|$k$-SAT}} in subexponential time as well. Equivalently, {{nowrap|if $s\_k>0$}} for {{nowrap|any $k>0$,}} then $s\_3>0$ as well, and the exponential time hypothesis would be {{nowrap|true.{{r|w03|ipz01}}}}

The limiting value $s\_\backslash infty$ of the sequence of numbers $s\_k$ is at most equal {{nowrap|to $s\_\{\backslash operatorname\{CNF\}\}$,}} where $s\_\{\backslash operatorname\{CNF\}\}$ is the infimum of the numbers $\backslash delta$ such that satisfiability of conjunctive normal form formulas without clause length limits can be solved in {{nowrap|time $O(2^\{\backslash delta\; n\})$.}} Therefore, if the strong exponential time hypothesis is true, then there would be no algorithm for general CNF satisfiability that is significantly faster than a brute-force search over all possible truth assignments. However, if the strong exponential time hypothesis fails, it would still be possible for $s\_\{\backslash operatorname\{CNF\}\}$ to equal {{nowrap|one.{{r|pw10}}}}

The exponential time hypothesis implies that many other problems in the complexity class SNP do not have algorithms whose running time is faster than $c^n$ for some {{nowrap|constant $c$.}} These problems include Graph coloring, finding Hamiltonian cycles, maximum cliques, maximum independent sets, and vertex cover on {{nowrap|$n$-vertex}} graphs. Conversely, if any of these problems has a subexponential algorithm, then the exponential time hypothesis could be shown to be {{nowrap|false.{{r|w03|ipz01}}}}

If cliques or independent sets of logarithmic size could be found in polynomial time, the exponential time hypothesis would be false. Therefore, even though finding cliques or independent sets of such small size is unlikely to be NP-complete, the exponential time hypothesis implies that these problems are {{nowrap|non-polynomial.{{r|w03|fk}}}} More generally, the exponential time hypothesis implies that it is not possible to find cliques or independent sets of size $k$ in {{nowrap|time $n^\{o(k)\}$.{{r|chkx}}}} The exponential time hypothesis also implies that it is not possible to solve the 3SUM problem (given $n$ real numbers, find $k$ of them that add to zero) in {{nowrap|time $n^\{o(k)\}$.}}

The strong exponential time hypothesis implies that it is not possible to find {{nowrap|$k$-vertex}} dominating sets more quickly than in {{nowrap|time $n^\{k-o(1)\}$.{{r|pw10}}}}

The exponential time hypothesis implies also that the weighted feedback arc set problem on tournaments does not have a parametrized algorithm with running {{nowrap|time $O(2^\{o(\backslash sqrt\{\backslash operatorname\{OPT\}\})\}n^\{O(1)\})$.}} It does however have a parameterized algorithm with running {{nowrap|time $O(2^\{O(\backslash sqrt\{\backslash operatorname\{OPT\}\})\}n^\{O(1)\})$.{{r|ks}}}}

The strong exponential time hypothesis leads to tight bounds on the parameterized complexity of several graph problems on graphs of bounded treewidth. In particular, if the strong exponential time hypothesis is true, then the optimal time bound for finding independent sets on graphs of {{nowrap|treewidth $w$}} {{nowrap|is $\backslash bigl(2-o(1)\backslash bigr)^w\; n^\{O(1)\}$,}} the optimal time for the dominating set problem {{nowrap|is $\backslash bigl(3-o(1)\backslash bigr)^w\; n^\{O(1)\}$,}} the optimum time for maximum cut {{nowrap|is $\backslash bigl(2-o(1)\backslash bigr)^w\; n^\{O(1)\}$,}} and the optimum time for {{nowrap|$k$-coloring}} {{nowrap|is $\backslash bigl(k-o(1)\backslash bigr)^w\; n^\{O(1)\}$.{{r|cfk}}}} Equivalently, any improvement on these running times would falsify the strong exponential time {{nowrap|hypothesis.{{r|lms}}}} The exponential time hypothesis also implies that any fixed-parameter tractable algorithm for edge clique cover must have double exponential dependence on the {{nowrap|parameter.{{r|cpp}}}}

In the three-party set disjointness problem in communication complexity, three subsets of the integers in some {{nowrap|range $[1,m]$}} are specified, and three communicating parties each know two of the three subsets. The goal is for the parties to transmit as few bits to each other on a shared communications channel in order for one of the parties to be able to determine whether the intersection of the three sets is empty or nonempty. A trivial {{nowrap|$m$-bit}} communications protocol would be for one of the three parties to transmit a bitvector describing the intersection of the two sets known to that party, after which either of the two remaining parties can determine the emptiness of the intersection. However, if there exists a protocol that solves the problem with {{nowrap|$o(m)$ communication}} and {{nowrap|$2^\{o(m)\}$ computation,}} it could be transformed into an algorithm for solving {{nowrap|$k$-SAT}} in {{nowrap|time $O(1.74^n)$}} for any fixed {{nowrap|constant $k$,}} violating the strong exponential time hypothesis. Therefore, the strong exponential time hypothesis implies either that the trivial protocol for three-party set disjointness is optimal, or that any better protocol requires an exponential amount of {{nowrap|computation.{{r|pw10}}}}

If the exponential time hypothesis is true, then 3-SAT would not have a polynomial time algorithm, and therefore it would follow that P ≠ NP. More strongly, in this case, 3-SAT could not even have a quasi-polynomial time algorithm, so NP could not be a subset of QP. However, if the exponential time hypothesis fails, it would have no implication for the P versus NP problem. A padding argument proves the existence of NP-complete problems for which the best known running times have the form $O(2^\{n^c\})$ {{nowrap|for ,}} and if the best possible running time for 3-SAT were of this form, then P would be unequal to NP (because 3-SAT is NP-complete and this time bound is not polynomial) but the exponential time hypothesis would be false.

In parameterized complexity theory, because the exponential time hypothesis implies that there does not exist a fixed-parameter-tractable algorithm for maximum clique, it also implies that {{nowrap|W[1] ≠ FPT.{{r|chkx}}}} It is an important open problem in this area whether this implication can be reversed: does {{nowrap|W[1] ≠ FPT}} imply the exponential time hypothesis? There is a hierarchy of parameterized complexity classes called the M-hierarchy that interleaves the W-hierarchy in the sense that, for {{nowrap|all $i$,}} {{nowrap|$\backslash mathsf\{M\}[i]\backslash subseteq\backslash mathsf\{W\}[i]\backslash subseteq\backslash mathsf\{M\}[i+1]$;}} for instance, the problem of finding a vertex cover of size $k\backslash log\; n$ in an {{nowrap|$n$-vertex}} graph with {{nowrap|parameter $k$}} is complete {{nowrap|for M[1].}} The exponential time hypothesis is equivalent to the statement that {{nowrap|M[1] ≠ FPT}}, and the question of whether $\backslash mathsf\{M\}[i]\backslash subseteq\backslash mathsf\{W\}[i]$ for $i>1$ is also {{nowrap|open.{{r|fg}}}}

It is also possible to prove implications in the other direction, from the failure of a variation of the strong exponential time hypothesis to separations of complexity classes.

As {{harvtxt|Williams|2010}} shows, if there exists an algorithm $A$ that solves Boolean circuit satisfiability in time $2^n/f(n)$ for some superpolynomially growing {{nowrap|function $f$,}} then NEXPTIME is not a subset of P/poly. Williams shows that, if algorithm $A$ exists, and a family of circuits simulating NEXPTIME in P/poly also existed, then algorithm $A$ could be composed with the circuits to simulate NEXPTIME problems nondeterministically in a smaller amount of time, violating the time hierarchy theorem. Therefore, the existence of algorithm $A$ proves the nonexistence of the family of circuits and the separation of these two complexity {{nowrap|classes.{{r|w10}}}}

• Savitch's theorem, showing that a similar exponential gap cannot hold for space complexity

{{reflist|refs=

{{citation

| last1 = Chen | first1 = Yijia

| last2 = Eickmeyer | first2 = Kord

| last3 = Flum | first3 = Jörg

| editor1-last = Thilikos | editor1-first = Dimitrios M.

| editor2-last = Woeginger | editor2-first = Gerhard J.

| contribution = The exponential time hypothesis and the parameterized clique problem

| doi = 10.1007/978-3-642-33293-7_4

| pages = 13–24

| publisher = Springer

| series = Lecture Notes in Computer Science

| title = Parameterized and Exact Computation – 7th International Symposium, IPEC 2012, Ljubljana, Slovenia, September 12–14, 2012, Proceedings

| volume = 7535

| year = 2012| citeseerx = 10.1.1.680.8401

}}

{{citation

| last1= Calabro | first1= Chris

| last2= Impagliazzo | first2= Russel | author2-link = Russell Impagliazzo

| last3= Paturi | first3 = Ramamohan

| contribution = The Complexity of Satisfiability of Small Depth Circuits

| doi = 10.1007/978-3-642-11269-0_6

| series = Lecture Notes in Computer Science | volume = 5917

| title = Parameterized and Exact Computation, 4th International Workshop, IWPEC 2009, Copenhagen, Denmark, September 10-11, 2009, Revised Selected Papers

| pages = 75–85

|year = 2009| citeseerx = 10.1.1.331.764

}}

{{citation

| last1 = Chen | first1 = Jianer

| last2 = Huang | first2 = Xiuzhen

| last3 = Kanj | first3 = Iyad A.

| last4 = Xia | first4 = Ge

| doi = 10.1016/j.jcss.2006.04.007

| issue = 8

| journal = Journal of Computer and System Sciences

| pages = 1346–1367

| title = Strong computational lower bounds via parameterized complexity

| volume = 72

| year = 2006| doi-access = free

}}

{{citation

|last1=Cygan|first1=Marek

|last2=Fomin|first2=Fedor V.

|last3=Kowalik|first3=Lukasz

|last4=Lokshtanov|first4=Daniel

|last5=Marx|first5=Daniel

|last6=Pilipczuk|first6=Marcin

|last7=Pilipczuk|first7=Michal

|last8=Saurabh|first8=Saket

|year=2015

|title=Parameterized Algorithms

|publisher=Springer

|isbn=978-3-319-21274-6

|page=555}}

{{citation

| last1 = Cygan | first1 = Marek

| last2 = Pilipczuk | first2 = Marcin

| last3 = Pilipczuk | first3 = Michał

| doi = 10.1137/130947076

| issue = 1

| journal = SIAM Journal on Computing

| mr = 3448348

| pages = 67–83

| title = Known algorithms for edge clique cover are probably optimal

| volume = 45

| year = 2016| arxiv = 1203.1754

| s2cid = 11264145

}}

{{citation

| last1 = Feige | first1 = Uriel | author1-link = Uriel Feige

| last2 = Kilian | first2 = Joe

| journal = Chicago Journal of Theoretical Computer Science

| pages = 1–20

| title = On limited versus polynomial nondeterminism

| volume = 1

| year = 1997| doi = 10.4086/cjtcs.1997.001 | doi-access = free }}

{{citation

| last1 = Flum | first1 = Jörg

| last2 = Grohe | first2 = Martin | author2-link = Martin Grohe

| contribution = 16. Subexponential Fixed-Parameter Tractability

| isbn = 978-3-540-29952-3

| pages = 417–451

| publisher = Springer-Verlag

| series = EATCS Texts in Theoretical Computer Science

| title = Parameterized Complexity Theory

| year = 2006}}

{{citation

| last1 = Impagliazzo | first1 = Russell | author1-link = Russell Impagliazzo

| last2 = Paturi | first2 = Ramamohan

| contribution = The Complexity of k-SAT

| doi = 10.1109/CCC.1999.766282

| pages = 237–240

| title = Proc. 14th IEEE Conf. on Computational Complexity

| year = 1999| isbn = 978-0-7695-0075-1 | s2cid = 442454 }}

{{citation

| last1 = Impagliazzo | first1 = Russell | author1-link = Russell Impagliazzo

| last2 = Paturi | first2 = Ramamohan

| last3 = Zane | first3 = Francis

| doi = 10.1006/jcss.2001.1774

| journal = Journal of Computer and System Sciences

| pages = 512–530

| title = Which problems have strongly exponential complexity?

| volume = 63

| citeseerx = 10.1.1.66.3717

| year = 2001

| issue = 4}}

{{citation

| last1 = Karpinski | first1 = Marek | author1-link = Marek Karpinski

| last2 = Schudy | first2 = Warren

| title = Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament

| journal = Proc. ISAAC 2010, Part I

| volume = 6506 | pages = 3–14

| year = 2010

| doi=10.1007/978-3-642-17517-6_3

| arxiv = 1006.4396| series = Lecture Notes in Computer Science | isbn = 978-3-642-17516-9 | s2cid = 16512997 }}

{{citation

| last1 = Lokshtanov

| first1 = Daniel

| last2 = Marx

| first2 = Dániel

| last3 = Saurabh

| first3 = Saket

| contribution = Known algorithms on graphs of bounded treewidth are probably optimal

| year = 2011

| arxiv = 1007.5450

| doi = 10.1137/1.9781611973082.61

| title = Proc. 22nd ACM/SIAM Symposium on Discrete Algorithms (SODA 2011)

| pages = 777–789| s2cid = 1810488

}}

{{citation

| last1 = Pătraşcu | first1 = Mihai | author1-link = Mihai Pătrașcu (computer scientist)

| last2 = Williams | first2 = Ryan|authorlink2=Ryan Williams (computer scientist)

| contribution = On the possibility of faster SAT algorithms

| pages = 1065–1075

| title = Proc. 21st ACM/SIAM Symposium on Discrete Algorithms (SODA 2010)

| url = http://people.csail.mit.edu/mip/papers/sat-lbs/paper.pdf

| year = 2010}}

{{citation

| last = Schöning | first = Uwe

| contribution = A probabilistic algorithm for $k$-SAT and constraint satisfaction problems

| doi = 10.1109/SFFCS.1999.814612

| pages = 410–414

| publisher = IEEE Computer Society

| title = 40th Annual Symposium on Foundations of Computer Science, FOCS '99, 17-18 October, 1999, New York, NY, USA

| year = 1999| s2cid = 1230959

}}

{{citation

| last = Williams | first = Ryan |authorlink=Ryan Williams (computer scientist)

| contribution = Improving exhaustive search implies superpolynomial lower bounds

| doi = 10.1145/1806689.1806723

| location = New York, NY, USA

| pages = 231–240

| publisher = ACM

| title = Proc. 42nd ACM Symposium on Theory of Computing (STOC 2010)

| year = 2010| isbn = 9781450300506 | citeseerx = 10.1.1.216.1299 | s2cid = 651703 }}

{{citation

| last = Woeginger

| first = Gerhard

| authorlink = Gerhard J. Woeginger

| doi = 10.1007/3-540-36478-1_17

| title = Combinatorial Optimization — Eureka, You Shrink!

| pages = 185–207

| publisher = Springer-Verlag

| contribution = Exact algorithms for NP-hard problems: A survey

| url = http://www.win.tue.nl/~gwoegi/papers/exact.pdf

| year = 2003

| volume = 2570

| series = Lecture Notes in Computer Science

| isbn = 978-3-540-00580-3

| citeseerx = 10.1.1.168.5383

| s2cid = 289357

| access-date = 2011-03-31

| archive-date = 2020-09-30

| archive-url = https://web.archive.org/web/20200930104811/http://www.win.tue.nl/~gwoegi/papers/exact.pdf

| url-status = dead

}}

}}

{{refbegin}}

• {{citation

| last1 = Dantsin | first1 = Evgeny

| last2 = Wolpert | first2 = Alexander

| contribution = On moderately exponential time for SAT

| doi = 10.1007/978-3-642-14186-7_27

| pages = 313–325

| publisher = Springer-Verlag

| series = Lecture Notes in Computer Science

| title = Theory and Applications of Satisfiability Testing–SAT 2010

| volume = 6175

| year = 2010| isbn = 978-3-642-14185-0}}

{{refend}}

{{Computational hardness assumptions}}

Category:Computational hardness assumptions