Exponential Time Hypothesis
A foundational assumption in computational complexity theory asserting that NP-complete problems such as 3-SAT have no subexponential-time algorithms; it is widely used to derive fine-grained lower bounds.
Timeline (last 90 days)
Several frontier AI labs claim that their models have achieved a breakthrough in computational complexity theory, refuting the exponential time hypothesis (ETH).
ETH asserts that for NP-complete problems such as 3-SAT, there is no algorithm that runs in subexponential time (that is, O(2^{o(n)})).
If ETH were overturned, many lower-bound results in complexity theory would no longer hold, and it could even affect the foundations of cryptography.
Any work claiming to refute ETH must undergo formal verification and peer review, and the information currently public falls far short of that standard.
AI models may merely have found fast solutions on specific small-scale instances, but this cannot refute ETH, because ETH concerns asymptotic behavior.
All Facts (5)
ETH asserts that for NP-complete problems such as 3-SAT, there is no algorithm that runs in subexponential time (that is, O(2^{o(n)})).
50%UnverifiedIf ETH were overturned, many lower-bound results in complexity theory would no longer hold, and it could even affect the foundations of cryptography.
50%UnverifiedAny work claiming to refute ETH must undergo formal verification and peer review, and the information currently public falls far short of that standard.
50%UnverifiedAI models may merely have found fast solutions on specific small-scale instances, but this cannot refute ETH, because ETH concerns asymptotic behavior.
50%UnverifiedSeveral frontier AI labs claim that their models have achieved a breakthrough in computational complexity theory, refuting the exponential time hypothesis (ETH).
50%