Insider Brief
- OpenAI has enlisted outside researchers to examine an AI-generated proof that it says overturns a longstanding assumption about the difficulty of certain computing problems.
- The claim could affect some assumptions used to assess quantum computing’s advantages, but does not itself establish a practical improvement in classical computing.
- A separate academic collaboration will examine OpenAI ’s claimed mathematical existence proofs for quantum field theories, including quantum chromodynamics.
OpenAI has enlisted outside researchers to examine an AI-generated proof that it says overturns a longstanding assumption about computing’s limits, according to a company news release that identifies three scientific advances under scrutiny.
The claim concerns the Exponential Time Hypothesis , or ETH, which describes how quickly the difficulty of certain logic problems grows. The claim could matter to quantum computing because predictions of a quantum computer’s advantage sometimes depend on assumptions about what ordinary computers can — and cannot — do.
A group led by Russell Impagliazzo and Ramamohan Paturi of the University of California, San Diego , and Ryan Williams of MIT will verify and explain the work, according to OpenAI’s announcement . Impagliazzo and Paturi helped formulate the hypothesis. OpenAI says the proof has been checked in Lean, a mathematical verification system, and released for public examination.
What the Computing Claim Means
The hypothesis concerns whether a computer can find a combination of true-or-false values that satisfies a set of logical conditions — and how quickly the time required grows as the problem gets larger.
Think of a scheduling puzzle with many interlocking requirements, such as, at least one of several people must attend a meeting, while other combinations are prohibited. Checking a proposed schedule can be straightforward, but finding one that meets every condition can become much harder as the requirements multiply.
ETH holds that even the best computer program cannot avoid a steep rise in the time needed to solve these logic problems as they grow larger. Put practically, it proposes a limit on how much researchers can tame the problem’s rapidly growing computational demands. Work by Impagliazzo, Paturi and Francis Zane connects that assumption to the difficulty of other problems, including graph coloring and finding particular groups within networks.
A disproof would challenge those assumed limits, but it would not automatically make large problems manageable.
For example, a method can be “subexponential,” meaning its running time grows more slowly than the exponential growth the hypothesis predicts, and still be impractically slow. For example, a calculation requiring two raised to the square root of the number of variables would take roughly a trillion steps for a problem with 1,600 variables. A theoretical improvement can also involve overhead that outweighs its benefits on problems small enough to run.
Nor would disproving ETH, by itself, settle P versus NP, which is the broader question of whether problems whose answers can be checked efficiently can also be solved efficiently. Subexponential running time can remain much slower than the polynomial running time at issue in that question.
Should Quantum Researchers Care?
On reason quantum computing researchers are likely to follow this examination is because some arguments about the difficulty of simulating quantum computers rely on related assumptions.
In one example , a team of researchers examined classical methods for calculating quantum circuit amplitudes — the numerical quantities used to determine measurement probabilities.
The researchers found limits on how quickly certain classical methods can simulate quantum circuits. They also identified broader limits based on the Strong Exponential Time Hypothesis, a related assumption about computing difficulty. Those broader conclusions would need another basis if the assumption proves false, while the findings that do not depend on it would still hold.
It also illustrates why changes in complexity theory require careful interpretation. Losing an argument that a calculation must be difficult does not supply a fast way to perform it. The practical question remains whether researchers can construct better classical algorithms and show where they work.
For the quantum community, one task may be focused on the need to identify which comparisons depend on the challenged assumptions and which rest on independent mathematical results or measured performance. The announcement alone does not establish a change in practical quantum advantage.
Examining the Proof
OpenAI says its proof has been checked using Lean, software designed to verify mathematical reasoning. To use it, researchers must express a proof in a precise mathematical language. The software then checks whether each step follows logically from the definitions and assumptions provided.
That offers more assurance than an AI-generated explanation that simply sounds convincing. But the software checks the statement it has been given. Researchers still need to make sure that statement accurately captures the computing problem OpenAI says it has resolved, and examine the assumptions behind the proof.
The outside collaboration will also work to explain how the proof works and what other researchers can learn from it. Even if the claim holds up, a mathematical result about the possibility of faster computation does not necessarily provide a method that runs quickly on today’s computers. Establishing its practical value would require further research.
A Separate Quantum Physics Claim
OpenAI also announced claimed mathematical existence proofs for quantum field theories, including quantum chromodynamics, which describes interactions involving quarks and gluons. A collaboration led by physicist David Gross will examine that work; the underlying AI-produced materials are being withheld while the group prepares its account.
The announcement includes a claim concerning the existence of pure Yang-Mills theory. That addresses part of the Clay Mathematics Institute’s Yang-Mills problem, whose requirements also include establishing a mass gap. An existence claim alone should therefore not be described as a solution to the full Millennium Prize problem.