The Exponential Time Hypothesis Is False [pdf]

Original Article ↗ Hacker News Discussion ↗

A new preprint from OpenAI claims to disprove the Exponential Time Hypothesis by giving a subexponential-time algorithm for 3-SAT, a flagship NP-complete problem. Commenters highlight that this is a major theoretical breakthrough that rules out a widely used hardness assumption and weakens confidence (slightly) in the belief that P≠NP, while still falling far short of a practical or polynomial-time solution and leaving most NP problems potentially exponential. Much of the conversation revolves around what the specific time bound really implies, why it does not automatically make all NP problems subexponential or break cryptography, and how “galactic” algorithms like this may nevertheless shift intuitions about what kinds of algorithms are possible.

Significance and relation to P vs NP

  • Many commenters see this as a huge theoretical result, “in the same league” as P vs NP, but emphasize it does not resolve P vs NP.
  • ETH being false removes a widely used assumption; a lot of prior work that depended on ETH/SETH may need revisiting.
  • Some interpret it as weakening confidence in P≠NP; others argue it doesn’t really move the needle, except to show our intuitions about “hard” problems were off.

What the result actually claims

  • ETH said k‑SAT (typically 3‑SAT) requires time ~2^{Ω(n)}.
  • The paper gives a subexponential algorithm, roughly 2^{n / √log n}, so ETH is false.
  • Thread repeatedly corrects a misconception: this does not prove NP≠EXP or NP⊊EXP.

Reductions and why NP isn’t proven subexponential

  • Key nuance: NP problems reduce to SAT in polynomial time, but polynomial reductions can blow up instance size.
  • Bounds of the form 2^{o(n)} don’t automatically carry through arbitrary polynomial reductions; one would need 2^{n^{o(1)}}.
  • Therefore, 3‑SAT being subexponential does not imply all NP problems are subexponential.
  • It does transfer to problems linearly reducible to SAT (e.g., certain counting problems listed in the paper).

ELI5 attempts and complexity intuition

  • Several comments offer lay explanations of SAT, NP, and ETH, stressing:
    • NP = efficiently verifiable (with a hint), not necessarily efficiently solvable.
    • Subexponential can still be astronomically large; there is a vast gap between polynomial and exponential time.

Practical impact and “galactic” algorithms

  • SAT‑solver experts call the algorithms “galactic”: constants are so huge that real-world instances remain better served by existing solvers.
  • Real SAT instances are often much easier than worst-case; no immediate performance gains are expected.

Broader implications and reactions

  • Some see this as shifting intuition slightly toward “maybe clever algorithms exist we haven’t imagined,” aligning with older views that many problems might admit faster algorithms.
  • Others worry about whether “efficient” in complexity theory matches real-world notions, suggesting P vs NP might be a poorly posed proxy for practical efficiency.
  • There is curiosity and speculation about impacts on cryptography, but the thread notes no current cryptosystems are obviously broken by this result.