← All problems

Strong Exponential Time Hypothesis

1 year old · documented by

The iterated logarithm function is defined recursively by

log⁡∗(n)={0n≤1;log⁡∗(log⁡n)+1n>1.\log^*(n) = \begin{cases}0 & n \le 1; \\ \log^*(\log n)+1 & n > 1.\end{cases}

For a positive integer kk, kk-SAT asks whether a Boolean formula with nn variables has a satisfying assignment. Strong Exponential Time Hypothesis. For every δ>0\delta>0 there is a positive integer kk such that kk-SAT instances with nn variables cannot be solved in time O(2n(1−δ))O(2^{n(1-\delta)}) by a randomized algorithm. SETH is a standard fine-grained complexity assumption underlying conditional lower bounds for the problems studied in the paper.

References
  1. Josh Alman and Yunfeng Guan, “Finer-Grained Hardness of Kernel Density Estimation”, arXiv:2407.02372 (2024).

Progress summary

Refreshed
Open

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 kk-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.

Sources

Solutions 0

No solutions have been posted yet.