Exponential time hypothesis
Encyclopedia
In computational complexity theory
, the exponential time hypothesis is an unproven computational hardness assumption formalized by stating that 3-SAT (or any of several related NP-complete
problems) cannot be solved in subexponential time in the worst case. The exponential time hypothesis, if true, would imply that P ≠ NP. It can be used to show that many computational problems are equivalent in complexity, in the sense that if one of them has a subexponential time algorithm then they all do.
is the problem of testing whether a Boolean formula, in conjunctive normal form
with at most k variables per clause, can be made to be true by some assignment of Boolean values to its variables.
For each integer k ≥ 2, define a real number sk to be the infimum
of the real numbers δ for which there exists an algorithm solving k-SAT in time O(2δn), where n is the number of variables in the given k-SAT instance. Then s2 = 0, because 2-SAT can be solved in polynomial time. The exponential time hypothesis is the conjecture
that, for every k > 2, sk > 0. Clearly, s3 ≤ s4 ≤ ...,
so it is equivalent to assume that s3 > 0; the positivity of the remaining numbers sk follows automatically from this assumption.
Some sources define the exponential time hypothesis to be the slightly weaker statement that 3-SAT cannot be solved in time 2o(n). If there existed an algorithm to solve 3-SAT in time 2o(n), then clearly s3 would equal one. However, it is consistent with current knowledge that there could be a sequence of 3-SAT algorithms, each with running time O(2δin) for a sequence of numbers δ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.
Because the numbers s3, s4, ... form a monotonic sequence that is bounded above by one, they must converge to a limit s∞. The strong exponential time hypothesis is the assumption that the limiting value s∞ of the sequence of numbers sk equals one.
An important tool in this area is the sparsification lemma of , which shows that, for any ε > 0, any k-CNF formula can be replaced by O(2εn) simpler 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εn) 3-CNF formulas, each with a linear number of variables, such that the original k-CNF formula is satisfiable if and only 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 k-SAT in subexponential time as well. Equivalently, if sk > 0 for any k > 3, then s3 > 0 as well, and the exponential time hypothesis would be true.
The limiting value s∞ of the sequence of numbers sk is at most equal to sCNF, where sCNF is the infimum of the numbers δ such that satisfiability of conjunctive normal form formulas without clause length limits can be solved in time O(2δ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 testing all possible truth assignments. However, if the strong exponential time hypothesis fails, it would still be possible for sCNF to equal one.
do not have algorithms whose running time is faster than cn for some constant c. These problems include graph k-colorability
, finding Hamiltonian cycles, maximum cliques, maximum independent sets, and vertex cover
on n-vertex graphs. Conversely, if any of these problems has a subexponential algorithm, then the exponential time hypothesis could be shown to be false.
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 non-polynomial. More generally, the exponential time hypothesis implies that it is not possible to find cliques or independent sets of size k in time no(k). The exponential time hypothesis also implies that it is not possible to solve the k-SUM
problem (given n real numbers, find k of them that add to zero) in time no(k).
The strong exponential time hypothesis implies that it is not possible to find k-vertex dominating sets more quickly than in time nk − o(1).
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 treewidth w is , the optimal time for the dominating set
problem is , the optimum time for maximum cut
is , and the optimum time for k-coloring is . Equivalently, any improvement on these running times would falsify the strong exponential time hypothesis.
, three subsets of the integers in some 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 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 o(m) communication and 2o(m) computation, it could be transformed into an algorithm for solving k-SAT in time O(1.74n) for any fixed 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 computation.
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 W[1] ≠ FPT
. It is an important open problem in this area whether this implication can be reversed: does 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 all i, ; for instance, the problem of finding a vertex cover
of size in an n-vertex graph with parameter k is complete for M[1]. The exponential time hypothesis is equivalent to the statement that , and the question of whether M[i] = W[i] for i > 1 is also open.
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 shows, if there exists an algorithm A that solves Boolean circuit satisfiability in time 2n/ƒ(n) for some superpolynomially growing function ƒ, 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 classes.
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, the exponential time hypothesis is an unproven computational hardness assumption formalized by stating that 3-SAT (or any of several related NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
problems) cannot be solved in subexponential time in the worst case. The exponential time hypothesis, if true, would imply that P ≠ NP. It can be used to show that many computational problems are equivalent in complexity, in the sense that if one of them has a subexponential time algorithm then they all do.
Definition
k-SATBoolean satisfiability problem
In computer science, satisfiability is the problem of determining if the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate to TRUE...
is the problem of testing whether a Boolean formula, in conjunctive normal form
Conjunctive normal form
In Boolean logic, a formula is in conjunctive normal form if it is a conjunction of clauses, where a clause is a disjunction of literals.As a normal form, it is useful in automated theorem proving...
with at most k variables per clause, can be made to be true by some assignment of Boolean values to its variables.
For each integer k ≥ 2, define a real number sk to be the infimum
Infimum
In mathematics, the infimum of a subset S of some partially ordered set T is the greatest element of T that is less than or equal to all elements of S. Consequently the term greatest lower bound is also commonly used...
of the real numbers δ for which there exists an algorithm solving k-SAT in time O(2δn), where n is the number of variables in the given k-SAT instance. Then s2 = 0, because 2-SAT can be solved in polynomial time. The exponential time hypothesis is the conjecture
Conjecture
A conjecture is a proposition that is unproven but is thought to be true and has not been disproven. Karl Popper pioneered the use of the term "conjecture" in scientific philosophy. Conjecture is contrasted by hypothesis , which is a testable statement based on accepted grounds...
that, for every k > 2, sk > 0. Clearly, s3 ≤ s4 ≤ ...,
so it is equivalent to assume that s3 > 0; the positivity of the remaining numbers sk follows automatically from this assumption.
Some sources define the exponential time hypothesis to be the slightly weaker statement that 3-SAT cannot be solved in time 2o(n). If there existed an algorithm to solve 3-SAT in time 2o(n), then clearly s3 would equal one. However, it is consistent with current knowledge that there could be a sequence of 3-SAT algorithms, each with running time O(2δin) for a sequence of numbers δ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.
Because the numbers s3, s4, ... form a monotonic sequence that is bounded above by one, they must converge to a limit s∞. The strong exponential time hypothesis is the assumption that the limiting value s∞ of the sequence of numbers sk equals one.
Implications for satisfiability
It is not possible for sk to equal s∞ for any finite k: as showed, there exists a constant α such that sk ≤ s∞(1 − α/k). Therefore, if the exponential time hypothesis is true, there must be infinitely many values of k for which sk differs from sk + 1.An important tool in this area is the sparsification lemma of , which shows that, for any ε > 0, any k-CNF formula can be replaced by O(2εn) simpler 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εn) 3-CNF formulas, each with a linear number of variables, such that the original k-CNF formula is satisfiable if and only 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 k-SAT in subexponential time as well. Equivalently, if sk > 0 for any k > 3, then s3 > 0 as well, and the exponential time hypothesis would be true.
The limiting value s∞ of the sequence of numbers sk is at most equal to sCNF, where sCNF is the infimum of the numbers δ such that satisfiability of conjunctive normal form formulas without clause length limits can be solved in time O(2δ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 testing all possible truth assignments. However, if the strong exponential time hypothesis fails, it would still be possible for sCNF to equal one.
Implications for other search problems
The exponential time hypothesis implies that many other problems in the complexity class SNPSNP (complexity)
In computational complexity theory, SNP is a complexity class containing a limited subset of NP based on its logical characterization in terms of graph-theoretical properties...
do not have algorithms whose running time is faster than cn for some constant c. These problems include graph k-colorability
Graph coloring
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...
, finding Hamiltonian cycles, maximum cliques, maximum independent sets, and vertex cover
Vertex cover
In the mathematical discipline of graph theory, a vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set....
on n-vertex graphs. Conversely, if any of these problems has a subexponential algorithm, then the exponential time hypothesis could be shown to be false.
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 non-polynomial. More generally, the exponential time hypothesis implies that it is not possible to find cliques or independent sets of size k in time no(k). The exponential time hypothesis also implies that it is not possible to solve the k-SUM
3SUM
In computational complexity theory, 3SUM is the following computational problem conjectured to require roughly quadratic time:There is a simple algorithm to solve 3SUM in O time. This is the fastest algorithm known in models that do not decompose the integers into bits, but matching lower bounds...
problem (given n real numbers, find k of them that add to zero) in time no(k).
The strong exponential time hypothesis implies that it is not possible to find k-vertex dominating sets more quickly than in time nk − o(1).
The strong exponential time hypothesis leads to tight bounds on the parameterized complexity
Parameterized complexity
Parameterized complexity is a branch of computational complexity theory in computer science that focuses on classifying computational problems according to their inherent difficulty with respect to multiple parameters of the input. The complexity of a problem is then measured as a function in those...
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 treewidth w is , the optimal time for the dominating set
Dominating set
In graph theory, a dominating set for a graph G = is a subset D of V such that every vertex not in D is joined to at least one member of D by some edge...
problem is , the optimum time for maximum cut
Maximum cut
For a graph, a maximum cut is a cut whose size is at least the size of any other cut. The problem of finding a maximum cut in a graph is known as the max-cut problem.The problem can be stated simply as follows...
is , and the optimum time for k-coloring is . Equivalently, any improvement on these running times would falsify the strong exponential time hypothesis.
Implications in communication complexity
In the three-party set disjointness problem in communication complexityCommunication complexity
The notion of communication complexity was introduced by Yao in 1979,who investigated the following problem involving two separated parties . Alice receives an n-bit string x and Bob another n-bit string y, and the goal is for one of them to compute a certain function f with the least amount of...
, three subsets of the integers in some 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 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 o(m) communication and 2o(m) computation, it could be transformed into an algorithm for solving k-SAT in time O(1.74n) for any fixed 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 computation.
Implications in structural complexity
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. There exist NP-complete problems for which the best known running times have the form O(2nc) for c < 1, 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 W[1] ≠ FPT
Parameterized complexity
Parameterized complexity is a branch of computational complexity theory in computer science that focuses on classifying computational problems according to their inherent difficulty with respect to multiple parameters of the input. The complexity of a problem is then measured as a function in those...
. It is an important open problem in this area whether this implication can be reversed: does 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 all i, ; for instance, the problem of finding a vertex cover
Vertex cover
In the mathematical discipline of graph theory, a vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set....
of size in an n-vertex graph with parameter k is complete for M[1]. The exponential time hypothesis is equivalent to the statement that , and the question of whether M[i] = W[i] for i > 1 is also open.
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 shows, if there exists an algorithm A that solves Boolean circuit satisfiability in time 2n/ƒ(n) for some superpolynomially growing function ƒ, then NEXPTIME
NEXPTIME
In computational complexity theory, the complexity class NEXPTIME is the set of decision problems that can be solved by a non-deterministic Turing machine using time O for some polynomial p, and unlimited space....
is not a subset of P/poly
P/poly
In computational complexity theory, P/poly is the complexity class of languages recognized by a polynomial-time Turing machine with a polynomial-bounded advice function. It is also equivalently defined as the class PSIZE of languages that have a polynomial-size circuits...
. 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
Time hierarchy theorem
In computational complexity theory, the time hierarchy theorems are important statements about time-bounded computation on Turing machines. Informally, these theorems say that given more time, a Turing machine can solve more problems...
. Therefore, the existence of algorithm A proves the nonexistence of the family of circuits and the separation of these two complexity classes.