Igor's KB Site

A personal website for information sharing

Follow me on GitHub

Breakthroughs Weekly — 15 November 2026

· breakthroughs · 2 items

Experts reproduce AI-found algorithms refuting the Exponential Time Hypothesis, and a review group backs an AI-built Yang-Mills existence proof; neither is peer reviewed.

Experts reproduce AI-found algorithms that refute the Exponential Time Hypothesis

Computational Complexity blog · 28 Oct 2026 · Complexity theory

OpenAI posted a preprint, with a Lean proof, giving an algorithm that decides satisfiability of k-CNF formulas for every fixed k, and even counts solutions, in polynomial time times 2^O(n log log n / √log n); the Lean version proves a slightly weaker bound. That is subexponential, so it refutes the Exponential Time Hypothesis and the stronger SETH, and Anthropic later released its own paper on the same question. Ryan O’Donnell and Shiva Kintali have written simpler follow-up proofs, and Lance Fortnow, who has not checked the argument himself, says it is safe to assume the hypothesis is dead; Impagliazzo, Paturi and Williams are running an open examination and say their role is not a certification. The algorithm gives nothing new for general NP problems such as Subset Sum, and all of these papers are preprints rather than reviewed publications.

Review group says OpenAI’s AI-built proof constructs four-dimensional Yang–Mills theory

Yang–Mills Group (GitHub) · 10 Nov 2026 · Mathematical physics

An independent group that reviews pure Yang–Mills submissions, reportedly chaired by Nobel laureate David Gross, has published its assessment of OpenAI’s 28 October Lean-checked submission. In the group’s opinion it proves that a quantum field theory obeying the Wightman axioms can be built as a scaling limit of four-dimensional lattice gauge theory for any simple compact gauge group. It does not show that the infinite-volume limit is unique or that a mass gap exists, so the Clay Millennium problem, which requires a mass gap, remains open. This is the group’s judgment rather than journal peer review, and press coverage reports that the reviewers say they do not yet fully understand the proof.


← All digests · Site home