Exponential time hypothesis

The exponential time hypothesis (ETH) is a conjecture in computational complexity theory asserting that satisfiability for Boolean formulas with clauses of bounded width requires exponential time in the worst case. In its standard deterministic form, ETH states that 3-satisfiability cannot be decided in time (2^{o(n)}), where (n) denotes the number of variables in the input formula. It provides a quantitative strengthening of the conjecture that P differs from NP.

ETH is not a claim that exhaustive search is optimal with an exact running time of (2^n). Algorithms for 3-satisfiability achieve running times substantially below that bound. The hypothesis instead asserts that every correct worst-case algorithm retains a positive constant in the exponent when its complexity is measured as a function of the number of variables.

Formal definition

For an integer (k\geq 3), let (k)-SAT denote the restriction of the Boolean satisfiability problem to formulas in conjunctive normal form whose clauses contain at most (k) literals. Its normalized exponential-time constant is commonly written as

[ s_k=\inf\left{\delta\geq 0: k\text{-SAT is decidable in } O!\left(2^{\delta n}\operatorname{poly}(n)\right)\right}. ]

The infimum ranges over deterministic algorithms, while (n) counts variables rather than clauses or symbols in the encoded input. In this notation, ETH is the statement

[ s_3>0. ]

Equivalently, there is a constant (c>0) such that no deterministic algorithm decides every 3-SAT instance with (n) variables in time (O(2^{cn})), apart from changes in the constant and polynomial factors implicit in the formulation. The notation (2^{o(n)}) includes running times such as (2^{\sqrt n}), (2^{n/\log n}), and every polynomial function of (n).

The choice of three literals per clause is not essential to the general phenomenon. Standard bounded-width transformations relate different values of (k), although their quantitative effects must be tracked when an exact exponential constant is under consideration. Width two is exceptional because 2-satisfiability is decidable in polynomial time.

Historical formulation

The hypothesis was formulated in 1999 through work by Russell Impagliazzo, Ramamohan Paturi, and You Watanabe on the asymptotic complexity of bounded-width satisfiability. Their formulation separated the qualitative distinction between polynomial and superpolynomial computation from the quantitative distinction between subexponential and exponential computation. The constants (s_k) provided a common scale on which algorithms for different clause widths could be compared.

This framework developed alongside exact algorithms that improved substantially on direct enumeration of all truth assignments. Such improvements established upper bounds below (2^n) without producing a sequence of algorithms whose exponential constants approach zero. ETH identifies the latter behavior, rather than any particular improvement over exhaustive search, as the decisive threshold.

The subsequent work of Russell Impagliazzo, Ramamohan Paturi, and Francis Zane established the sparsification lemma. That result supplied the structural connection between formulas measured by their variables and formulas whose numbers of clauses are also linearly bounded.

Sparsification and the choice of parameter

A general (k)-CNF formula on (n) variables may contain many clauses, making its encoded length considerably larger than (n). This creates a distinction between subexponential time in the number of variables and subexponential time in the total input length. The sparsification lemma controls that distinction for fixed clause width.

For every fixed (k) and every (\varepsilon>0), a (k)-CNF formula with (n) variables can be represented as a disjunction of at most (2^{\varepsilon n}) formulas, each containing only (O(n)) clauses. The representation is computable within (2^{\varepsilon n}\operatorname{poly}(n)) time, while the constants hidden by the linear bound depend on (k) and (\varepsilon).

Consequently, a subexponential algorithm for sparse 3-SAT would yield a subexponential algorithm for unrestricted 3-SAT. ETH can therefore be stated using formulas with linearly many clauses without changing its essential content. For sparse instances, the number of variables, the number of clauses, and the ordinary encoding length are linearly related up to constants determined by the representation.

Sparsification is also responsible for much of the stability of ETH-based lower bounds. It prevents the conclusion from depending on inputs that are artificially dense and permits reductions to begin with satisfiability instances whose structural size is proportional to their variable count.

Lower bounds derived from ETH

ETH functions as a starting assumption for conditional lower bounds. A reduction from sparse 3-SAT to another computational problem transfers the hypothesis when the reduction preserves the relevant size parameter up to a constant factor. If an instance with (n) variables becomes an instance of size at most (Cn), then a (2^{o(N)})-time algorithm for the target problem would imply a (2^{o(n)})-time algorithm for 3-SAT.

This reasoning yields conditional exclusions of subexponential algorithms for numerous NP-complete problems. For example, size-linear reductions connect satisfiability to appropriate formulations of graph coloring, independent set, and vertex cover. The precise conclusion depends on what the target problem counts as instance size; a lower bound stated in terms of vertices is not automatically equivalent to one stated in terms of edges or encoding bits.

Reductions with superlinear growth produce correspondingly weaker exponents. When a source instance of size (n) becomes a target instance of size (N=O(n^d)), ETH excludes a target running time of (2^{o(N^{1/d})}), rather than necessarily excluding (2^{o(N)}). ETH-based results therefore record parameter growth more closely than ordinary polynomial-time many-one reductions, for which any polynomial increase is generally sufficient.

The same quantitative principle appears in parameterized complexity. ETH rules out running times of the form (f(k)n^{o(k)}) for several parameterized problems when a reduction encodes a satisfiability instance into a parameter proportional to its structural width. These statements are stronger than classifications based only on W-hardness, because they constrain the exponent of the polynomial dependence on the main input size.

Relation to stronger hypotheses

The strong exponential time hypothesis concerns the limiting behavior of (s_k) as clause width increases. Its standard form states that

[ \lim_{k\to\infty}s_k=1. ]

SETH therefore asserts that satisfiability for unbounded fixed clause width approaches the (2^n) scale in its optimal exponential constant. ETH requires only that the constant for 3-SAT remain strictly positive, so it supports coarser lower bounds and does not determine whether the optimal 3-SAT exponent is close to one.

A separate randomized form, commonly called randomized ETH, replaces deterministic computation with bounded-error randomized algorithms. Deterministic ETH does not by itself exclude every subexponential randomized algorithm, since the two assumptions quantify over different computational models. Lower bounds involving randomization consequently identify the randomized hypothesis when that distinction affects the reduction.

ETH implies that 3-SAT lacks a polynomial-time algorithm and therefore implies (\mathrm{P}\ne\mathrm{NP}). The converse does not follow: the failure of polynomial-time algorithms remains compatible with complexities such as (2^{\sqrt n}), which are superpolynomial but subexponential. ETH occupies the stronger position by excluding this entire intermediate range for bounded-width satisfiability.

Logical status

ETH remains an unproved conjecture because an unconditional exponential lower bound for general algorithms solving 3-SAT lies beyond established lower-bound techniques. Restricted computational models admit stronger results, but such bounds do not extend automatically to unrestricted Turing machines or equivalent general models of computation.

The hypothesis is principally used to distinguish reductions that preserve fine-grained size from reductions that preserve only polynomial-time solvability. Its conclusions remain conditional: an ETH-based lower bound establishes that a specified algorithmic improvement would produce a subexponential algorithm for 3-SAT. It does not constitute an unconditional lower bound for the target problem.