OpenAI claims AI disproves Exponential Time Hypothesis

OpenAI claims its AI models have found a way to disprove the Exponential Time Hypothesis, a computer-science conjecture from 1999. The company published a 67-page paper describing a deterministic algorithm that counts satisfying assignments of puzzles in subexponential time. OpenAI says its AI found the disproof on October 16 and formalized it in Lean software on October 17. The paper is dated October 17 and revised on October 25.

Crypto Twitter users reacted to the claim by mistakenly believing it referred to Ethereum cryptocurrency. A user named Takumi posted on X claiming that algo traders slaughtered $ETH due to the announcement. Andrew Jiang commented that Vitalik Buterin has been quiet since the OpenAI announcement. MIT professor Ryan Williams previously criticized the proof drop as a 'DDOS attack on mathematicians'.

Russell Impagliazzo, Ramamohan Paturi, and Ryan Williams are leading the independent examination of the claim. The three computer scientists issued an open letter stating their involvement should not be taken as certification. OpenAI states that participants signed no non-disclosure agreements and worked unpaid. OpenAI contributed $5 million to the Simons Foundation to fund workshops and conferences for examining AI-produced results.