OpenAI announces proof refuting Exponential Time Hypothesis in Lean

На русском
1 min
OpenAI announces proof refuting Exponential Time Hypothesis in Lean

OpenAI has announced that it proved the Exponential Time Hypothesis is false and even verified it in Lean, sending shockwaves through the math and computer science communities.

The Exponential Time Hypothesis is a concept mainly used to set lower bounds for algorithms that find solutions to NP-complete problems. It asserts that if a problem is in this hard class, then no matter how efficient an algorithm you design, it cannot solve it faster than 2^O(n), i.e., faster than exponential time.

OpenAI claims to have proved that the Exponential Time Hypothesis is wrong for a certain subset of cases. If true, it raises the possibility that the optimal results of many problems whose conclusions were based on the hypothesis could be overturned. Am I seeing this right...?

https://x.com/danintheory/status/2114833682469122314?s=20

Original publication

Authors credited by the source: c4lvinlocked

Published by Holder based on an external source.