It states that satisfiability of 3-CNF Boolean formulas cannot be solved in subexponential time,
More precisely, the usual form of the hypothesis asserts the existence of a number
The exponential time hypothesis, if true, would imply that P ≠ NP, but it is a stronger statement.
It implies 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, and that many known algorithms for these problems have optimal or near-optimal time complexity.
The goal is to determine whether this expression can be made to be true by some assignment of Boolean values to its variables.
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
The exponential time hypothesis is the conjecture that they are all nonzero, or equivalently, that the smallest of them,
However, it is consistent with current knowledge that there could be a sequence of 3-SAT algorithms, each with running time
form a monotonic sequence that is bounded above by one, they must converge to a limit
: as Impagliazzo, Paturi & Zane (2001) showed, there exists a constant
[6] An important tool in this area is the sparsification lemma of Impagliazzo, Paturi & Zane (2001), which shows that, for every
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
such that satisfiability of conjunctive normal form formulas without clause length limits can be solved in time
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.
Conversely, if any of these problems has a subexponential algorithm, then the exponential time hypothesis could be shown to 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.
[7][9] More generally, the exponential time hypothesis implies that it is not possible to find cliques or independent sets of size
[10] The exponential time hypothesis also implies that it is not possible to solve the k-SUM problem (given
[14] In the three-party set disjointness problem in communication complexity, three subsets of the integers in some range
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.
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.
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
[10] It is an important open problem in this area whether this implication can be reversed: does 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 all
The exponential time hypothesis is equivalent to the statement that M[1] ≠ FPT, and the question of whether
[3] 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.
proves the nonexistence of the family of circuits and the separation of these two complexity classes.