Three layers of understanding
01 · Understand the problem
Some puzzles seem to get overwhelmingly harder as they grow. A new AI-generated argument claims that a famous prediction about how quickly this happens is wrong.
02 · Understand the contribution
The Exponential Time Hypothesis (ETH) asserts that 3-SAT admits no subexponential-time algorithm in the number of variables. OpenAI announced an AI-generated refutation and a Lean formalization; an external group is studying the implications.
03 · Academic context
ETH is a fine-grained complexity assumption, usually expressed as the absence of an algorithm with running time 2^o(n) for 3-SAT on n variables. A verified refutation would unsettle conditional lower bounds across algorithms and parameterized complexity. It would NOT, on its own, establish P=NP or that practical SAT instances are easy.
What this might change
Could require re-examining many conditional hardness results, but no practical speedup or cryptographic break is established by this announcement.
What is NOT established
High-impact provider claim. Raw proof material is public; independent technical analysis remains essential.