OpenAI and Anthropic claim faster algorithms for 3-SAT

OpenAI and Anthropic have published separate AI-generated claims about faster algorithms for 3-SAT, a problem at the centre of theoretical computer science. Both claims concern the exponential time hypothesis, a widely used assumption about how the hardest instances scale as they grow.

OpenAI released its claimed result on 26 October and named an independent group to examine it. Anthropic has separately published a paper and formal proof artefacts attributed to an internal Claude research model. The results are claims for researchers to scrutinise.

What is 3-SAT?

Imagine a list of conditions, each containing up to three statements that can be true or false. Each statement is a variable or its opposite. A condition is satisfied when at least one of its statements is true. The 3-SAT problem asks whether there is an assignment of true and false values that satisfies every condition at once.

As the number of variables grows, the number of possible assignments grows rapidly. The exponential time hypothesis, formulated by Russell Impagliazzo and Ramamohan Paturi, says that a general algorithm cannot solve every 3-SAT instance in subexponential time as a function of the number of variables.

OpenAI and Anthropic each claim an algorithm with a subexponential bound. If a claimed result holds under the standard definition, it would challenge that hypothesis and the assumptions used in many other complexity results.

What the checks cover

OpenAI says its system found the natural-language argument on 16 October and that a version was formalised in the Lean proof assistant the following day. Its review group is led by Impagliazzo, Paturi and MIT computer scientist Ryan Williams. OpenAI says the materials are public so the wider research community can examine them.

Anthropic’s repository describes a separate claimed algorithm and a Lean 4 formalisation. It says the result concerns the way running time grows for very large inputs. The repository also asks readers to inspect whether the formal statement accurately expresses the paper’s claim.

A proof assistant checks whether formal steps follow from the definitions and assumptions supplied to it. Experts still need to examine whether those definitions capture the mathematical claim and how the argument relates to existing results. A subexponential bound also leaves a wide gap to a polynomial-time algorithm, the distinction relevant to P versus NP.

OpenAI released two other research claims

OpenAI’s announcement also describes a claimed result on local smoothing, a question about how waves focus, with implications it identifies for the Kakeya and Stein restriction conjectures. The company released a natural-language manuscript and a Lean formalisation for that work.

The third claim concerns the mathematical existence of certain four-dimensional quantum field theories, including quantum chromodynamics. OpenAI says the researchers organising that collaboration chose to hold the AI-produced materials while they work on their own explanation. Each line of work now has its own path through expert examination.