An OpenAI preprint claims to disprove the Exponential Time Hypothesis (ETH), a foundational conjecture in computational complexity theory. If verified, this would imply that certain NP-hard problems can be solved significantly faster than currently believed, with major implications for complexity theory and cryptography. The paper generated significant discussion on Hacker News with 224 points and 96 comments.
Background
The Exponential Time Hypothesis, proposed by Impagliazzo and Paturi in 1999, posits that 3-SAT requires exponential time to solve. It is a widely used assumption in fine-grained complexity theory. This appears to be an OpenAI research preprint released in October 2026.
- Source
- Hacker News (RSS)
- Published
- Oct 27, 2026 at 05:59 AM
- Score
- 8.0 / 10