OpenAI says its model refuted the Exponential Time Hypothesis

A claim that almost every proof in algorithm design has rested on for twenty-five years is now up for review. OpenAI said one of its models wrote a paper refuting the Exponential Time Hypothesis. The company released the write-up and a Lean proof on GitHub for an outside group of computer scientists to check.

OpenAI announced three results in mathematics, computer science and physics, with named academics guiding the review of each. The Verge, which read the OpenAI post, said the company is calling the academics "shepherds". The math and computer science results sit in the openai/math repository, with Lean formalisations.

What the three papers say

The computer science paper is titled "The Exponential Time Hypothesis is False" in the GitHub history. It gives a deterministic algorithm that counts the satisfying assignments of fixed-width CNF formulas in subexponential time and polynomial space. The case of 3-SAT refutes the hypothesis. The Exponential Time Hypothesis was proposed in 1999. It is used across algorithm theory as the floor for how fast many problems can be solved.

The math paper proves local smoothing for the Euclidean wave equation. OpenAI says the proof also settles the Kakeya maximal and dimension conjectures in every spatial dimension above one. It also yields Stein's spherical restriction estimates inside the conjectured range. NYU professor Hong Wang was given a Fields Medal this year for the three-dimensional case of Kakeya. The Verge noted this.

The physics result has not been released in full. OpenAI calls it a rigorous existence proof. The proof covers interacting quantum field theories with gauge fields and fermions in four dimensions. That set includes Quantum Chromodynamics and a unified completion of the Standard Model, per OpenAI's description quoted by The Verge.

Who is checking what

For the computer science paper, OpenAI named Russell Impagliazzo and Ramamohan Paturi of UC San Diego. The two proposed the hypothesis in 1999. MIT professor Ryan Williams joins them. The group chose to make the write-up and Lean proof public straight away. They sent an open letter asking the community how to review AI-generated breakthroughs.

For the physics paper, OpenAI said Nobel laureate David Gross will lead the group. The group includes Michael Douglas, Arthur Jaffe, Igor Klebanov and Nikita Nekrasov.

The math result is released directly, with no shepherd group. OpenAI's own AGMAI panel of math advisers spoke one day before the announcement. The panel said AI companies should not pick certain people to see output first. It cited unequal access and biased selection as reasons, per The Verge. It asked labs to release output on scholarly repositories, with Lean-formalised proofs and funding for the people doing the checking.

A reader who builds products with a frontier model now has to think about verification in a new way. A model that writes a proof against a widely used claim can also write a wrong proof that looks right. Both read the same at first. The academic shepherd is the current answer. It works only when the output comes with a formal proof the reviewers can run. Teams relying on model output for high-stakes work can read the open letter from the computer science group. It is the shape of a standard being written in real time.

Source

OpenAI's math and computer science release is in openai/math/history.md. Reporting by Richard Lawler at The Verge.