Exponential Time Hypothesis
There is no -time algorithm which can determine whether a given 3SAT formula on variables is satisfiable.
Exponential Time Hypothesis. There is no -time algorithm which can determine whether a given 3SAT formula on variables is satisfiable.
This hypothesis is used to establish the quasipolynomial lower bound for planning in observable POMDPs; its status is open and it formalizes the conjectured absence of subexponential-time algorithms for 3SAT.
References
- Noah Golowich, Ankur Moitra and Dhruv Rohatgi, “Planning in Observable POMDPs in Quasipolynomial Time”, arXiv:2201.04735 (2022).
Progress summary
The hypothesis remains open: no independently verified faster-than-exponential algorithm for 3SAT has been established.
The Exponential Time Hypothesis, introduced by Impagliazzo, Paturi, and Zane, asserts that deciding 3SAT cannot be done in time . It remains a foundational conditional assumption in fine-grained complexity.
Known results
- The sparsification lemma gives equivalent variable-count and clause-count formulations (Impagliazzo, Paturi, and Zane, 1998).
- ETH is characterized through exponential-time bounds for and related problems (Impagliazzo and Paturi, 2001).
- ETH yields conditional quasipolynomial lower bounds for planning in observable POMDPs (Golowich, Moitra, and Rohatgi, 2022).
Current status (as of October 2026): The Exponential Time Hypothesis remains open; no independently verified proof or refutation of the -time claim is recorded.