Three letters have muddied the reading of a scientific announcement: ETH. In the work presented by OpenAI, they do not refer to Ethereum, but to the ‘Exponential Time Hypothesis’, a conjecture about the difficulty of certain computational problems. The company says its models have found a refutation of it. This would be a major theoretical result, but assessing it cannot be reduced to reading the paper’s title.
The material published in October 2026 makes it possible to distinguish OpenAI’s claim, the algorithm described and the work of understanding undertaken by researchers. It also helps rule out two hasty conclusions: this announcement does not resolve P versus NP and does not, by itself, provide a recipe for breaking cryptocurrencies.
A problem of satisfying rules
The problem being studied involves assigning ‘true’ or ‘false’ values to variables while satisfying a set of constraints. A variable can appear either directly or negated. In the case known as 3-SAT, each clause contains at most three of these elements; all the clauses must be made true simultaneously.
To picture the number of possibilities, imagine switches with two positions. Ten switches allow 1,024 configurations; twenty allow 1,048,576. This example illustrates the growth in the number of combinations, not the actual running time of a piece of software: an algorithm can avoid examining every one of them.
The ETH hypothesis therefore does not simply say that every configuration has to be tried. It posits a more general limit: not every instance of 3-SAT could be solved in subexponential time relative to the number of variables. Improving the base of an exponential growth is not enough to refute it. A different boundary has to be crossed in the way computing time increases.
This qualification changes the meaning of the announcement. It is not merely a slightly faster programme for difficult examples. The paper claims a method whose complexity bound contradicts the conjecture itself.
What the paper claims
In its 25 October version, the 67-page text presents a deterministic algorithm: its operation does not depend on random draws. It aims to count exactly the satisfying assignments of a formula, for clauses of a maximum size fixed in advance. This last condition matters: the parameter describing that size is not allowed to grow without constraint alongside the problem.
Counting the solutions also makes it possible to decide whether any exist. If the number obtained is zero, the formula is unsatisfiable; if it is positive, it is satisfiable. This move from counting to decision is what connects the announced result to ETH.
The paper claims subexponential time and polynomial memory use. These qualifications describe how resource requirements grow as the input size increases. They do not give a running time in seconds for a particular machine. Better theoretical behaviour at a very large scale can still come with costs that are too high for everyday problems.
This distinction guards against promises of premature practical use: the document presents a claimed mathematical result, not an available application whose speed has been measured here. No practical improvement to the software used by the reader can be inferred from its summary alone.
A formal proof does not replace the full explanation
In its presentation on 26 October, OpenAI says its models found the refutation on 16 October and that formalisation in Lean followed on 17 October. Lean is a proof assistant: it allows statements and reasoning to be represented in a language that can be checked by software. The company has published the paper and the formal materials for examination.
Such a system adds a valuable means of checking the work. It is nevertheless necessary to understand which statement was formalised, under which definitions, and how it corresponds to the scientific claim. Checking a file, interpreting the theorem and explaining its significance are related but different tasks. Reading an introductory article does not mean they have been carried out.
The challenge for the reader is not to choose between automatic trust and automatic rejection. The right approach is to identify the announced result and the steps that enable other specialists to reconstruct it.
Researchers distinguish examination from certification
Russell Impagliazzo, Ramamohan Paturi and Ryan Williams have launched an initiative for examination and discussion. In their letter of 26 October, they make clear that their participation does not amount to certification of the claim. They emphasise the importance of an understanding that other researchers can reconstruct, question and use.
This framework is particularly useful for a result presented as having been produced by AI. The origin of the text does not remove the need to make the proof intelligible. An advance becomes usable when its conditions, limits and enabling ideas can be explained beyond its initial publication package.
This does not mean that all previous work based on ETH becomes uninteresting. A conditional implication can remain correct even if its starting hypothesis is challenged. However, its use as an argument for difficulty must be reassessed in light of the result actually established.
Neither P versus NP nor a hacking tool
The paper states that its result does not imply a subexponential algorithm for every problem in the class NP. Translating one problem into another can increase its size: a favourable bound in one formulation therefore does not automatically transfer to all others.
Nor does it prove that every problem whose solution can be checked efficiently can also be solved efficiently, the question known as P versus NP. ‘Subexponential’ does not mean ‘polynomial’, let alone ‘instantaneous’.
The announcement is therefore worth following for its precise scientific claim. To assess its contribution, the next useful developments will be explanations of the algorithm that others can reconstruct, clarification of its consequences and, separately, any methods that might be usable in practice. Here, the acronym ETH is the beginning of a question in complexity theory, not a verdict on Ethereum.
Illustrative photograph: a discussion in front of a mathematics board. The people pictured are not identified as the authors or reviewers of the result.
Credit: Yan Krukau — Pexels, Pexels licence.
