Headline suggestion: OpenAI’s AI Claims to “Disprove ETH” — But It’s the Exponential Time Hypothesis, Not Ethereum
Quick take
- Don’t panic: OpenAI didn’t just wreck Ethereum. Crypto Twitter’s stunned reaction came from confusion over “ETH” — here it means the Exponential Time Hypothesis, a 1999 computer-science conject, not the blockchain token.
- OpenAI says an AI discovered a deterministic subexponential-time algorithm for counting solutions to 3‑SAT (a classic logic puzzle). If correct, that would refute ETH and reopen questions about how fast certain computational tasks can be solved.
- The claim is being independently scrutinized by leading theorists (including the original proposers), and major caveats mean practical consequences — and P vs NP — remain far from settled.
What happened
- On Oct. 16–17, OpenAI says a model produced a proposed disproof of the Exponential Time Hypothesis (ETH). The company published a 67‑page paper (initially dated Oct. 17 and revised Oct. 25) and a Lean formalization on GitHub — the same workflow used for hundreds of recent AI math manuscripts.
- The paper describes a deterministic algorithm that counts every satisfying assignment of 3‑SAT instances in subexponential time. Counting all solutions is strictly harder than merely deciding whether a solution exists, so if counting is subexponential then the decision problem follows.
- OpenAI framed the result as one that “reopens questions about how much faster these tasks could become” and could “help guide the search for better algorithms,” but added that turning such theoretical advances into practical improvements will take much more work.
Why this matters (but also why not yet)
- ETH (Exponential Time Hypothesis) is a foundational conjecture used to prove many conditional lower bounds across graph theory, computational biology, databases, geometry, and more. If ETH is false, many of those “probably intractable” limits might need rethinking.
- The result does not claim that every NP problem is subexponential, so the P vs NP question remains open.
- Practical impact is uncertain and likely far off. The paper’s gains are asymptotic — about behavior as problem size grows — and may not translate to faster algorithms on real-world instances.
Who’s checking the work
- Russell Impagliazzo and Ramamohan Paturi (two of ETH’s proposers, with Francis Zane) plus MIT’s Ryan Williams are leading independent scrutiny. They emphasized their involvement is not certification and called for careful, independent verification that others can reconstruct and test.
- OpenAI says contributors worked unpaid, signed no NDAs, and that it will publish raw data and fund a conference to aid review.
Rival AI labs join the fray
- Anthropic posted a paper credited to Claude (dated Oct. 26) that also claims a 2^o(n) time algorithm for 3‑SAT, noting the result is asymptotic and not about practical formula solving.
- This follows a broader pattern: advanced language models increasingly produce complex math outputs and machine-checked proofs (e.g., Claude formalizing Fermat’s Last Theorem in Lean). Mathematicians like Terence Tao have warned that even rumors of AI-led progress can trigger rapid, AI-powered follow-ups.
Funding and next steps
- OpenAI pledged a $5 million contribution to the Simons Foundation to support workshops, conferences, and programs that help researchers examine and build on AI-produced results.
- The community-led verification process will determine whether this is a genuine shift in complexity theory or an intriguing but ultimately flawed proof attempt. Either way, it highlights how AI is accelerating research cycles in deep theoretical fields.
Bottom line for crypto readers
- Short version: ETH here = Exponential Time Hypothesis, not Ethereum. No reason to expect immediate impacts on ETH price, Vitalik, or the blockchain. But this episode is a clear sign that AI is now a major player in high-end mathematics and theoretical computer science — and that could eventually ripple into cryptography, security, and other areas relevant to crypto infrastructure.
Quick take
- Don’t panic: OpenAI didn’t just wreck Ethereum. Crypto Twitter’s stunned reaction came from confusion over “ETH” — here it means the Exponential Time Hypothesis, a 1999 computer-science conject, not the blockchain token.
- OpenAI says an AI discovered a deterministic subexponential-time algorithm for counting solutions to 3‑SAT (a classic logic puzzle). If correct, that would refute ETH and reopen questions about how fast certain computational tasks can be solved.
- The claim is being independently scrutinized by leading theorists (including the original proposers), and major caveats mean practical consequences — and P vs NP — remain far from settled.
What happened
- On Oct. 16–17, OpenAI says a model produced a proposed disproof of the Exponential Time Hypothesis (ETH). The company published a 67‑page paper (initially dated Oct. 17 and revised Oct. 25) and a Lean formalization on GitHub — the same workflow used for hundreds of recent AI math manuscripts.
- The paper describes a deterministic algorithm that counts every satisfying assignment of 3‑SAT instances in subexponential time. Counting all solutions is strictly harder than merely deciding whether a solution exists, so if counting is subexponential then the decision problem follows.
- OpenAI framed the result as one that “reopens questions about how much faster these tasks could become” and could “help guide the search for better algorithms,” but added that turning such theoretical advances into practical improvements will take much more work.
Why this matters (but also why not yet)
- ETH (Exponential Time Hypothesis) is a foundational conjecture used to prove many conditional lower bounds across graph theory, computational biology, databases, geometry, and more. If ETH is false, many of those “probably intractable” limits might need rethinking.
- The result does not claim that every NP problem is subexponential, so the P vs NP question remains open.
- Practical impact is uncertain and likely far off. The paper’s gains are asymptotic — about behavior as problem size grows — and may not translate to faster algorithms on real-world instances.
Who’s checking the work
- Russell Impagliazzo and Ramamohan Paturi (two of ETH’s proposers, with Francis Zane) plus MIT’s Ryan Williams are leading independent scrutiny. They emphasized their involvement is not certification and called for careful, independent verification that others can reconstruct and test.
- OpenAI says contributors worked unpaid, signed no NDAs, and that it will publish raw data and fund a conference to aid review.
Rival AI labs join the fray
- Anthropic posted a paper credited to Claude (dated Oct. 26) that also claims a 2^o(n) time algorithm for 3‑SAT, noting the result is asymptotic and not about practical formula solving.
- This follows a broader pattern: advanced language models increasingly produce complex math outputs and machine-checked proofs (e.g., Claude formalizing Fermat’s Last Theorem in Lean). Mathematicians like Terence Tao have warned that even rumors of AI-led progress can trigger rapid, AI-powered follow-ups.
Funding and next steps
- OpenAI pledged a $5 million contribution to the Simons Foundation to support workshops, conferences, and programs that help researchers examine and build on AI-produced results.
- The community-led verification process will determine whether this is a genuine shift in complexity theory or an intriguing but ultimately flawed proof attempt. Either way, it highlights how AI is accelerating research cycles in deep theoretical fields.
Bottom line for crypto readers
- Short version: ETH here = Exponential Time Hypothesis, not Ethereum. No reason to expect immediate impacts on ETH price, Vitalik, or the blockchain. But this episode is a clear sign that AI is now a major player in high-end mathematics and theoretical computer science — and that could eventually ripple into cryptography, security, and other areas relevant to crypto infrastructure.