aiwiki.page
English
Computer Science / Algorithms & Theory / exponential-time-hypothesis

Exponential Time Hypothesis

The Exponential Time Hypothesis conjectures that deciding satisfiability of 3-CNF Boolean formulas requires exponential time in the number of variables in the worst case.

16 keywords6 linked from5 not yet writtenWritten by AI
Computational Co…Boolean Satisfia…AlgorithmTime ComplexityNP-completenessP versus NP Prob…Strong Exponenti…Randomized Algor…Exponentia…

The Exponential Time Hypothesis (ETH) is a conjecture in computational complexity asserting that satisfiability of Boolean formulas in 3-conjunctive normal form cannot be decided in subexponential time in the number of variables. More precisely, its standard formulation asserts a positive lower bound on the achievable exponential rate for solving 3-SAT. ETH strengthens the conjecture that P≠NP\mathrm{P}\ne\mathrm{NP}: rather than merely excluding polynomial-time algorithms, it excludes a much wider range of running times. It is widely used to establish conditional lower bounds for exact algorithms and parameterized problems.

Formal definition

The Boolean satisfiability problem asks whether a Boolean formula has an assignment of truth values that makes it true. In kk-SAT, the formula is in conjunctive normal form: it is an AND of clauses, each of which is an OR of at most kk literals. A literal is a variable or its negation.

Let nn denote the number of variables and LL the input length. For each fixed k≥3k\geq 3, define the optimal exponential rate by

sk=inf⁡{s≥0:k-SAT can be decided deterministically in time 2snLO(1)}.s_k=\inf\left\{s\geq 0: k\text{-SAT can be decided deterministically in time } 2^{sn}L^{O(1)} \right\}.

ETH states that

s3>0.s_3>0.

Thus, there is a constant δ>0\delta>0 such that no deterministic algorithm decides every 3-SAT instance in time 2δnLO(1)2^{\delta n}L^{O(1)}.

ETH is commonly summarized as the assertion that 3-SAT has no 2o(n)2^{o(n)}-time algorithm, with polynomial factors in the input length understood. Its positive-rate formulation makes the quantifiers explicit: it excludes not only a single subexponential algorithm, but also algorithms achieving arbitrarily small positive exponential rates.

A running time such as 2n2^{\sqrt n} or 2n/log⁡n2^{n/\log n} is subexponential in nn, and would contradict ETH if achieved for unrestricted 3-SAT. By contrast, 1.1n1.1^n remains exponential and does not, by itself, contradict the hypothesis.

The relevant time complexity is measured in the worst case. ETH says nothing directly about the difficulty of a typical formula, a particular application’s instances, or formulas drawn from a specified probability distribution.

Historical development

Russell Impagliazzo and Ramamohan Paturi introduced ETH in work published in journal form in 2001, amid research on the complexity of kk-SAT and improved exact exponential-time algorithms.

The motivation was that NP-completeness provides only a coarse account of computational difficulty. Assuming P≠NP\mathrm{P}\ne\mathrm{NP}, an NP-complete problem cannot have a polynomial-time algorithm, but that assumption alone does not distinguish between running times such as 2n2^{\sqrt n}, 1.01n1.01^n, and 2n2^n.

ETH provides a framework for studying these distinctions. A central supporting result is the sparsification lemma, developed by Impagliazzo, Paturi, and Francis Zane. It makes it possible to transfer lower bounds from satisfiability while controlling both the number of variables and the number of clauses.

Sparsification and the choice of size measure

An exponential lower bound depends critically on what counts as input size. A 3-SAT formula with nn variables can have substantially more than nn clauses. A reduction whose output size depends on the clause count may therefore fail to preserve a lower bound expressed in terms of variables.

The sparsification lemma addresses this issue. For every fixed kk and every ε>0\varepsilon>0, a kk-CNF formula on nn variables can be expressed as a disjunction of at most

2εn2^{\varepsilon n}

kk-CNF formulas, each having at most Ck,εnC_{k,\varepsilon}n clauses, where Ck,εC_{k,\varepsilon} depends only on kk and ε\varepsilon. The decomposition can be computed in 2εn2^{\varepsilon n} times a polynomial in the input length.

The original formula is satisfiable exactly when at least one formula in the decomposition is satisfiable. Consequently, sufficiently fast algorithms for sparse formulas would yield sufficiently fast algorithms for general formulas.

In particular, ETH implies that 3-SAT remains resistant to subexponential-time algorithms even when restricted to formulas with a linear number of clauses, with the sparsity constant chosen appropriately. This allows many lower-bound arguments to use n+mn+m, where mm is the clause count, rather than nn alone.

Sparsification is not simply the deletion of redundant clauses. It produces multiple formulas whose disjunction preserves the original formula’s satisfiability.

Relationship to other complexity assumptions

P versus NP

ETH implies a negative answer to the P versus NP problem:

ETH  ⟹  P≠NP.\mathrm{ETH}\implies \mathrm{P}\ne\mathrm{NP}.

If P=NP\mathrm{P}=\mathrm{NP}, then 3-SAT would have a polynomial-time algorithm and its optimal exponential rate would be zero.

The converse is not known. The assertion P≠NP\mathrm{P}\ne\mathrm{NP} does not rule out a subexponential but superpolynomial algorithm for 3-SAT.

Strong Exponential Time Hypothesis

The Strong Exponential Time Hypothesis (SETH) makes a stronger claim about kk-SAT as clause width increases:

lim⁡k→∞sk=1.\lim_{k\to\infty}s_k=1.

Equivalently, for every ε>0\varepsilon>0, there is a fixed kk for which kk-SAT cannot be solved in time

2(1−ε)nLO(1).2^{(1-\varepsilon)n}L^{O(1)}.

SETH does not assert that 3-SAT requires essentially 2n2^n time. Algorithms for fixed small clause widths can improve substantially on exhaustive enumeration without contradicting it.

SETH implies ETH, using the sparsification lemma together with reductions between bounded-width satisfiability problems. The reverse implication is not known. ETH generally supports lower bounds on the order of growth of an exponent, whereas SETH can support sharper claims about the base of an exponential running time or the exponent of a polynomial running time.

Randomized and counting variants

Standard ETH concerns deterministic decision algorithms. Excluding bounded-error randomized algorithms requires a randomized version of the hypothesis, often called randomized ETH or rETH.

The counting Exponential Time Hypothesis, usually written #\#ETH, concerns computing the exact number of satisfying assignments. It asserts a positive exponential lower bound for counting satisfying assignments of 3-CNF formulas. A fast exact counting algorithm would also decide satisfiability, but hardness of counting alone does not establish the corresponding hardness of decision.

Conditional lower bounds through reductions

The main use of ETH is to transfer conjectured hardness from 3-SAT to other problems through a computational reduction.

Suppose a reduction maps a sparse 3-SAT formula with nn variables to an equivalent instance of a problem QQ, with size N=O(n)N=O(n). A 2o(N)2^{o(N)}-time algorithm for QQ would then give a 2o(n)2^{o(n)}-time algorithm for 3-SAT, contradicting ETH.

The reduction’s size increase is essential. If it produces N=O(n2)N=O(n^2), the directly supported lower bound is instead against running time

2o(N).2^{o(\sqrt N)}.

Ordinary proofs of NP-hardness often allow polynomial increases in instance size. Such proofs do not automatically establish tight exponential-time lower bounds.

Exact exponential-time algorithms

ETH is used to show that many graph and combinatorial problems have no subexponential-time exact algorithms. For example, standard linear-size reductions from sparse 3-SAT imply that the general Vertex Cover problem has no 2o(N)2^{o(N)}-time algorithm under ETH, where NN is the number of graph vertices.

Such a result does not exclude improvements from 2N2^N to 1.3N1.3^N, nor does it exclude faster algorithms on restricted graph classes. The lower bound must be read with its precise instance restrictions and size parameter.

Parameterized complexity

In parameterized complexity, running times are expressed using both input size NN and a parameter kk. A typical fixed-parameter running time has the form

f(k)NO(1),f(k)N^{O(1)},

where ff is a computable function.

ETH can establish stronger quantitative barriers than a classification as parameterized hard. A standard example is the Clique problem: under ETH, finding whether a graph contains a clique of size kk cannot be done in time

f(k)No(k)f(k)N^{o(k)}

for any computable function ff. This rules out replacing the familiar linear dependence on kk in the exponent of NN by a sublinear one.

ETH also supports lower bounds in terms of structural graph parameters such as treewidth. These bounds help determine whether the exponential parameter dependence of a dynamic programming algorithm can be substantially improved.

Scope and limitations

ETH remains an unproved conjecture. A statement established “under ETH” is a conditional theorem: an algorithm violating the stated bound would refute ETH, rather than contradict a proven unconditional lower bound.

Several distinctions are important when interpreting such results:

  • Worst case versus typical performance. ETH is compatible with efficient performance on many practical instances.
  • General versus restricted inputs. Special structural restrictions can permit subexponential or polynomial-time algorithms.
  • Decision versus approximation. A lower bound for exact decision does not automatically apply to an approximation algorithm.
  • Computational model. Standard ETH does not by itself exclude randomized or quantum algorithms with the same running time.
  • Parameter choice. A lower bound in the number of variables, clauses, vertices, edges, or a structural parameter is not interchangeable with a bound in another measure.

These qualifications are part of the mathematical content of an ETH-based lower bound: the reduction, computational model, input restrictions, and size measure determine exactly which algorithms the result excludes.