Strong Exponential Time Hypothesis
The iterated logarithm function is defined recursively by
For a positive integer , -SAT asks whether a Boolean formula with variables has a satisfying assignment. Strong Exponential Time Hypothesis. For every there is a positive integer such that -SAT instances with variables cannot be solved in time by a randomized algorithm. SETH is a standard fine-grained complexity assumption underlying conditional lower bounds for the problems studied in the paper.
References
- Josh Alman and Yunfeng Guan, “Finer-Grained Hardness of Kernel Density Estimation”, arXiv:2407.02372 (2024).
Progress summary
The hypothesis remains unproved, with no credible disproof or resolution found.
SETH asserts that, in sufficiently large dimensions of the SAT problem, exhaustive search cannot be improved by any fixed exponential factor. It was formulated by Russell Impagliazzo and Ramamohan Paturi in 1999 and is used to derive conditional lower bounds for other problems.
Known results
- Impagliazzo and Paturi, 1999: formulated SETH as a hardness hypothesis for -SAT.
- Cygan, Dell, Lokshtanov, Marx, Nederlof, Okamoto, Paturi, Saurabh, and Wahlström: derived conditional lower bounds for Hitting Set, Set Splitting, NAE-SAT, and related problems.
- Backurs and Indyk: showed that a sufficiently faster Edit Distance algorithm would contradict SETH.
- Belova, Kulikov, Mihajlin, Ratseeva, Reznikov, and Sharipov, 2023: studied SETH-related barriers without proving or refuting SETH.
Current status (as of October 2026): SETH remains an unproved assumption; its truth or falsity is open, while its conditional consequences are established.
Solutions 0
No solutions have been posted yet.