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 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, 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 s_k 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 s₂ = 0, because 2-SAT can be solved in polynomial time. The exponential time hypothesis is the conjecture that, for every k > 2, s_k > 0. Clearly, s₃ ≤ s₄ ≤ ..., so it is equivalent to assume that s₃ > 0; the positivity of the remaining numbers s_k 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 2^o(n). If there existed an algorithm to solve 3-SAT in time 2^o(n), then clearly s₃ 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.

...
Wikipedia