OpenAI claims to disprove the Exponential Time Hypothesis
OpenAI researchers announced they have disproved the Exponential Time Hypothesis — a foundational conjecture in computational complexity holding that 3-SAT cannot be solved faster than 2^n time — a result the hypothesis' own co-proposer Russell Impagliazzo called 'shocking news.' Implications include potential speedups in chip design optimisation and faster attacks on certain cryptographic schemes.
- ETH underpins hardness assumptions behind several widely-deployed encryption schemes
- Co-proposer Impagliazzo called the result 'shocking'; formal peer review is pending
- Practical cryptographic impact is contested — timelines for real-world risk are years, not months