OpenAI says an AI model refuted the Exponential Time Hypothesis; outside review begins
The claim leaves P vs NP open. The review's organizers, including two of ETH's proposers, say it is no certification.
Key figure: 3, results OpenAI announced Oct. 26. Math, computer science and physics; all await outside checks. Source: OpenAI.[1]
Key points
- OpenAI says its model found the ETH disproof Oct. 16.[1]
- Two of ETH’s proposers and an MIT computer scientist will organize an open review, not a certification.[3]
- Anthropic posted its own ETH claim hours later.[6][7]
- A Microsoft and Georgia Tech paper maps 23 ways AI agents fail users.[9]
OpenAI's claim
OpenAI said Monday its models refuted the Exponential Time Hypothesis, which holds that 3-SAT, a canonical hard problem, needs exponential time.[1] Its 67-page preprint gives a subexponential algorithm; OpenAI’s Lean proof checks a weaker, still subexponential time bound than the paper’s sharpest.[1][2] That is still not polynomial time, so P vs NP stays open.[2][6]
Who checks it
UC San Diego’s Russell Impagliazzo and Ramamohan Paturi, who proposed ETH, and an MIT computer scientist are organizing an open review.[1] “Our involvement should not be taken as certification of the claim,” they wrote.[3][5] Hours later, Anthropic posted its own ETH refutation claim.[6][7]
What it means for OpenAI
Why it matters: OpenAI is private, so the test is credibility, not a share price. The claim landed the day Anthropic filed for its IPO, and a day after AGMAI, a math advisory group OpenAI had pledged to consult, urged AI labs not to give chosen experts first access, The Verge reported.[4][8]
Agents that fail their users
Microsoft Research and Georgia Tech built MANDATE, 23 agent failure types in seven groups, from 163,487 Reddit posts and a study of 73 users. The most severe failures were rated hardest to notice, the arXiv paper says.[9]
Thanks to our friends at DAIR.AI for highlighting the research.
Intel agrees to buy Classiq
Intel agreed to buy quantum software maker Classiq, pending regulatory approvals. It gave no price; Calcalist reported $2.3 billion, and Bloomberg, citing people familiar with the matter, about $2.3 billion.[10][11][12]
Exhibit 1. OpenAI’s three claims and who checks them As announced Oct. 26, 2026
| Claim | Materials | Outside check |
|---|---|---|
| ETH is false (computer science) | Paper and Lean proof public | Impagliazzo, Paturi and an MIT computer scientist |
| Local smoothing, all dimensions (math) | Paper and Lean proof public | Researchers self-organize |
| QCD existence proof (physics) | Held back by the group | Group led by David Gross |
Source: OpenAI.[1] All three are OpenAI’s claims; none has been independently confirmed. Table: New Street.
Exhibit 2. Where AI agents fail the people who use them % of 6,623 failure instances in Reddit posts, by MANDATE group
| MANDATE group | Failure instances | Share |
|---|---|---|
| Termination and resource (incl. running without progress) | 1,921 | 29.0% |
| Adherence (ignored instructions, plan drift) | 1,778 | 26.8% |
| Misrepresentation (false reports of work) | 1,148 | 17.3% |
| Autonomy boundary (overstepping scope) | 1,037 | 15.7% |
| Social norm (flattery, overconfidence) | 449 | 6.8% |
| Exposure of information | 163 | 2.5% |
| Deceptive optimization | 127 | 1.9% |
Source: Microsoft Research and Georgia Tech, arXiv:2610.34748.[9] Group shares are New Street sums of the paper’s category counts. Table: New Street.
Notes
- Vendor and company claims are attributed to the company that made them.
Sources
- Working with academic communities to build scientific understanding, (OpenAI, "Working with academic communities to build scientific understanding," Oct. 26, 2026. (accessed Oct. 28, 2026). Three announced results: a proof of the local smoothing conjecture in every dimension (which OpenAI says also resolves the Kakeya and Stein restriction conjectures), a refutation of the Exponential Time Hypothesis, and an existence proof for QCD and a unified completion of the Standard Model. OpenAI says its AI found the ETH disproof Oct. 16, 2026, and formalized it in Lean Oct. 17. The ETH group is led by Russell Impagliazzo (UC San Diego), Ramamohan Paturi (UC San Diego) and an MIT computer scientist; Impagliazzo and Paturi, with Francis Zane, proposed ETH. The math result was released for researchers to organize their own efforts; the physics group, led by David Gross, is holding back the AI-produced materials and writing the work up itself. OpenAI says "Finding such algorithms, and turning theoretical advances into practical improvements, will require significant further research" and that it does not seek academic credit. OpenAI agreed to the group's requests to make all raw data public and to fund a conference.)
- The Exponential Time Hypothesis is False, (OpenAI, "The Exponential Time Hypothesis is False," preprint dated Oct. 17, 2026, revised Oct. 25, 2026, 67 pages (PDF page count). (accessed Oct. 28, 2026). Gives a deterministic, polynomial-space algorithm that exactly counts satisfying assignments of k-CNF formulas in subexponential time. Lean scope note (OpenAI, lean/docs/378.md): the Lean proof covers a weaker time bound than the manuscript's sharpest one. GitHub commit history shows the files posted Oct. 26, 2026, 20:52 UTC. A subexponential bound is still superpolynomial, so the result does not resolve P vs NP (see also note 6).)
- Message to the TCS Community on ETH (Russell Impagliazzo, Ramamohan Paturi and an MIT computer scientist, "Message to the TCS Community on ETH," open letter, Oct. 26, 2026. (accessed Oct. 28, 2026). "Our involvement should not be taken as certification of the claim. A result of this significance requires careful, independent scrutiny." The letter's resource list also links Anthropic's refutation.)
- OpenAI announces three big science discoveries and a new way to work with academics, (The Verge, "OpenAI announces three big science discoveries and a new way to work with academics," Oct. 26, 2026. (accessed Oct. 28, 2026). Reports that the AGMAI math advisory group said the day before that "we recommend that AI companies do not adopt" the practice of designating certain people to receive AI output first.)
- OpenAI says its AI model has disproved the Exponential Time Hypothesis, (The Next Web, "OpenAI says its AI model has disproved the Exponential Time Hypothesis," Oct. 26, 2026. (accessed Oct. 28, 2026). Independent report of the claim and of the review group's statement that its role is not an endorsement.)
- A 2^o(n) Time Algorithm for 3-SAT, (Anthropic, "A 2^o(n) Time Algorithm for 3-SAT," by Claude (Anthropic), paper and Lean 4 formalization, anthropics/formal-math, eth folder. (accessed Oct. 28, 2026). Commit dated Oct. 27, 2026, 03:07 UTC (11:07 p.m. ET Oct. 26). README: "The result is purely asymptotic and says nothing about solving formulas in practice." The paper says the result "does not bear on the P vs NP question directly.")
- A 2^o(n) Time Algorithm for 3-SAT, (Hexagon, "A 2^o(n) Time Algorithm for 3-SAT," contributed by Anthropic, v1 deposited Oct. 27, 2026. (accessed Oct. 28, 2026). Provenance statement: the core algorithm "was found on October 16 by an internal Claude research model"; "Independently and concurrently, an internal model at OpenAI claims to have proven a similar result.")
- PBC, Form S-1 registration statement, filed Oct. 26, 2026. https://www.sec.gov/Archives/edgar/data/2130357/000162828026067168/anthropicpbc-sx1.htm (accessed Oct. 27, 2026). Cited only for the filing date.
- Babysitting AI Agents: A User-Centered Taxonomy and Study of Agentic Delegation Failures (Shravika Mittal, Sunnie S. Y. Kim, Scott Counts, Jennifer Neville, Debarati Das and Philippe Laban (Georgia Tech, Microsoft Research, Microsoft), "Babysitting AI Agents: A User-Centered Taxonomy and Study of Agentic Delegation Failures," arXiv:2610.34748, submitted Oct. 26, 2026. (accessed Oct. 28, 2026). 163,487 Reddit posts from eight subreddits (January 2025 to June 2026); MANDATE taxonomy of 23 failure categories in seven groups; 4,367 posts with 6,623 failure instances; study of 73 experienced AI agent users. Severity and noticeability are strongly negatively related (Spearman's rho of minus 0.61). Unbounded or idle execution is the largest category (1,017 instances, 15.4%) and has one of the least mature research bases. Exhibit 2 group totals are New Street sums of the category counts in Section 3.3.)
- Intel to Acquire Classiq to Create a Full-stack Quantum Computing Platform, (Intel, "Intel to Acquire Classiq to Create a Full-stack Quantum Computing Platform," Oct. 26, 2026, 4:30 p.m. ET. (accessed Oct. 28, 2026). Definitive agreement; expected to close in the first half of 2027, subject to regulatory approvals. No price disclosed.)
- Intel to acquire Israeli quantum startup Classiq for $2.3 billion, (Calcalist (Ctech), "Intel to acquire Israeli quantum startup Classiq for $2.3 billion," Oct. 26, 2026. (accessed Oct. 28, 2026). Cash and stock.)
- Intel to Buy Quantum Startup Classiq for About $2.3 Billion, (Bloomberg News (via Bloomberg Law), "Intel to Buy Quantum Startup Classiq for About $2.3 Billion," Oct. 27, 2026. (accessed Oct. 28, 2026). About $2.3 billion, according to people familiar with the matter; Intel did not disclose a price.)