Math Conjectures

Exponential Time Hypothesis

OPENLandmarkConjectureProposed 1999 · Standard version

Canonical statement

No deterministic algorithm decides satisfiability of 33-CNF formulas with nn variables in time 2o(n)2^{o(n)}, where a 33-CNF is a conjunction of clauses, each containing at most three literals.
View source LaTeX
No deterministic algorithm decides satisfiability of
\(3\)-CNF formulas with \(n\) variables in time \(2^{o(n)}\), where a
\(3\)-CNF is a conjunction of clauses, each containing at most three
literals.
TCS-009:[ImpagliazzoPaturi2001ETH][ImpagliazzoPaturiZane2001][LokshtanovMarxSaurabh2011]
Theoretical computer scienceOperations research

Notes

The Exponential Time Hypothesis, formulated by Impagliazzo and Paturi in 1999, sharpens P≠NPP\ne NP into a quantitative statement: no deterministic algorithm decides satisfiability of 33-CNF formulas on nn variables in time 2o(n)2^{o(n)} [ImpagliazzoPaturi2001ETH]. Whereas P≠NPP\ne NP only rules out polynomial time, the hypothesis excludes even mildly subexponential time for 33-SAT, and is therefore a stronger assumption.

A key technical ingredient is the sparsification lemma of Impagliazzo, Paturi and Zane, which expresses any 33-CNF as a disjunction of subexponentially many formulas, each with only linearly many clauses; this makes the hypothesis robust under changes of the size parameter and turns it into a versatile basis for reductions [ImpagliazzoPaturiZane2001]. On this foundation a large body of conditional lower bounds has been built, yielding essentially tight running-time bounds for many exact, parameterized and approximation problems [LokshtanovMarxSaurabh2011].

The hypothesis is unproven: present unconditional techniques cannot rule out subexponential algorithms for 33-SAT, and since the hypothesis implies P≠NPP\ne NP, any proof must go beyond all current lower-bound methods.

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.