Exponential time hypothesis

In computational complexity theory, the exponential time hypothesis is an unproven computational hardness assumption that was formulated by Impagliazzo & Paturi (1999). The hypothesis states that 3-SAT (or any of several, but not all, NP-complete problems) cannot be solved in subexponential time in the worst case. The exponential time hypothesis, if true, would imply that P ≠ NP, but it is a stronger statement. 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. In computational complexity theory, the exponential time hypothesis is an unproven computational hardness assumption that was formulated by Impagliazzo & Paturi (1999). The hypothesis states that 3-SAT (or any of several, but not all, NP-complete problems) cannot be solved in subexponential time in the worst case. The exponential time hypothesis, if true, would imply that P ≠ NP, but it is a stronger statement. 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. k-SAT is the problem of testing whether a Boolean expression, 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 k-SAT can be algorithmically solved 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. Moreover, s3 ≤ s4 ≤ ..., since the difficulty does not decrease with growing k. The exponential time hypothesis is the conjecture that sk > 0 for every k > 2, or, equivalently, that s3 > 0. 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 s3 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δ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 (SETH) is the conjecture that s∞=1. Another variant is the non-uniform exponential time hypothesis, a strengthening of the second phrasing of the ETH, 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 time 2o(n). It is not possible for sk to equal s∞ for any finite k: as Impagliazzo, Paturi & Zane (2001) 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 Impagliazzo, Paturi & Zane (2001), 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 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 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.