# A challenge to the Exponential Time Hypothesis

- ID: exponential-time-hypothesis
- Provider: OpenAI
- Published: 2026-10-26
- Editorial check: 2026-10-29
- Status: independent-review-pending
- Evidence: AI-produced disproof; Lean formalization reported
- Source: https://openai.com/index/building-scientific-understanding-with-academic-communities/
- Public article: https://appliedfrontier.nl/en/discoveries/exponential-time-hypothesis/

## Plain-language explanation

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.

## Research 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.

## Academic interpretation

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.

## Implications

Could require re-examining many conditional hardness results, but no practical speedup or cryptographic break is established by this announcement.

## Caveat

High-impact provider claim. Raw proof material is public; independent technical analysis remains essential.

This is an editorial summary, NOT an independent mathematical proof check.