AI’s Math Challenge Could Rewrite How Computer Scientists Measure Difficulty

TechCrunch reported that OpenAI and Anthropic have presented results claiming to refute the Exponential Time Hypothesis, or ETH, a central assumption about how much computation certain problems require as their inputs become larger.

The claim concerns a boundary that computer scientists use to separate problems that may be practically solvable from those expected to become impossibly expensive. If the result survives scrutiny, researchers may have to reconsider a large body of work that treats some problems as inherently resistant to fast algorithms.

The implications are theoretical first. The claim does not prove that P equals NP, the famous unsolved question about whether every problem whose answer can be checked quickly can also be solved quickly. It does, however, challenge assumptions that have helped researchers reason about computational hardness, optimization and the limits of algorithmic progress.

A claim about the foundations

OpenAI said in a research announcement that it had produced three AI-generated mathematical and computer-science results. One of them is a claimed refutation of ETH. The company also said it had formalized the work in Lean, a system used to express mathematical arguments in a form that can be checked by software, and released materials publicly for examination.

OpenAI’s public repository contains a preprint dated October 25, 2026. It claims a subexponential algorithm for fixed-width CNF problems and links to both the paper and its formalization.

In simpler terms, the proposed result says that a family of problems generally expected to require exponential resources could instead be handled with a slower-than-polynomial process that is still substantially faster than a true exponential one. That distinction matters most when inputs grow. An algorithm that looks manageable for a small problem can become unusable when the input doubles, while a subexponential approach could change the scale at which computation remains practical.

The result is not being presented as a finished scientific consensus. OpenAI said Russell Impagliazzo, Ramamohan Paturi and Ryan Williams would lead an independent examination. Impagliazzo and Paturi introduced ETH in 1999, making their involvement especially significant. Their task is not simply to reproduce a company announcement, but to determine whether the proof works, whether its assumptions are sound and whether the claimed algorithm delivers what the paper says it does.

Why verification is different this time

Mathematical research has always depended on other experts checking difficult arguments. AI-generated proofs raise the pressure because the work may be produced quickly, contain unfamiliar strategies and arrive with enough technical detail to overwhelm the number of people able to review it.

Williams’s public posts and message to the theoretical computer science community say that he, Impagliazzo and Paturi were asked to organize an open and independent examination of OpenAI’s claimed refutation. The accompanying message stresses that their participation is not certification of the result.

That distinction gives the process a useful shape. A respected researcher is not being asked to lend a name to a breakthrough. Instead, a group is being assembled to create a shared examination in which specialists can divide the proof, test its unfamiliar steps and discuss whether the argument changes existing theory.

According to TechCrunch’s account, Williams said some parts of the proof appeared routine, while two or three sections looked unusually unfamiliar and potentially important. That combination is characteristic of the current AI research moment. A machine-generated result may contain long stretches that follow known methods, alongside a small number of steps that are either genuinely original or simply difficult to interpret.

The public release also changes who can participate. Researchers do not have to rely on a presentation from the lab or wait for a conventional journal process. They can inspect the preprint, examine the formalization and attempt to identify gaps or consequences. Lean may help by checking whether formal statements follow from formal premises, although translating a mathematical idea into a formal system does not by itself establish that the idea is useful, relevant or correctly connected to the original claim.

Another laboratory, another claim

Anthropic’s formal-math repository presents a claimed deterministic subexponential-time algorithm for 3-SAT, attributed to an internal Claude research model, with associated formalization materials.

The parallel claims from two frontier AI labs make the episode harder to treat as a single unusual announcement. They also make independent review more urgent. Similar language can conceal important differences in the problems addressed, the meaning of “subexponential” and the conditions under which an algorithm operates. Researchers will need to establish whether the approaches are valid, whether they are genuinely new and whether either result reaches the full scope implied by ETH.

The sources reviewed for this article contain no published objection to the claims. The documented response is instead an organized effort to inspect them, and the involvement of senior researchers is explicitly described as independent examination rather than endorsement.

What could change if the work holds

A validated refutation would not instantly make every hard problem easy. It could, however, force researchers to revisit papers that use ETH to prove that certain algorithms cannot exist within particular time bounds. Some lower-bound arguments, complexity classifications and explanations of why optimization problems are difficult might need to be rewritten.

The practical consequences would arrive more slowly. Better algorithms could eventually affect scheduling, search, planning and other computational tasks. Security systems could also face questions if their safety relies on assumptions about computational difficulty. TechCrunch reported that Williams said OpenAI had checked for immediate cryptographic vulnerabilities and was reasonably confident that the result did not create one.

The larger shift may concern scientific practice. If AI systems continue producing results that span hundreds of pages, depend on unfamiliar ideas and resist quick human understanding, publication norms will have to adapt. Labs may need to release formal proofs, machine-readable artifacts, clear records of prior work and funding for independent conferences or review groups.

The future suggested by these claims is not one in which mathematicians disappear. It is one in which mathematicians become investigators of machine-generated territory, deciding which paths lead to new knowledge and which end in elegant-looking errors. For computer science, that may be the most important result of all.