Two AI labs say they broke a 27-year-old rule of computer science, and they shipped the Lean proofs 🧮

Some of the most interesting AI news this week has nothing to do with chatbots. On 26 October OpenAI posted a paper titled, rather boldly, "The Exponential Time Hypothesis is False". Hours later Anthropic published its own paper, "A 2^o(n) Time Algorithm for 3-SAT", credited to an internal research Claude model. Two labs, two different routes, the same claim, and both come with a Lean 4 formalization you can build yourself.

What ETH actually says

3-SAT is the classic hard puzzle: you have n on/off switches and a list of rules, each rule naming three switches, and you want a setting that satisfies every rule. Brute force means trying all 2^n settings. Decades of clever work shaved that down (Anthropic's paper lists the previous deterministic record as O(1.328^n)), but it always stayed exponential. In 1999 Russell Impagliazzo and Ramamohan Paturi proposed the Exponential Time Hypothesis: there is no way out of that exponential climb.

Both papers say there is. OpenAI describes a deterministic algorithm that exactly counts the satisfying assignments of any k-CNF formula in subexponential time and polynomial space. Anthropic's algorithm also counts solutions, in 2^O(n log log n / √log n) time, and its paper lists tensor networks and rank among its key ideas. Counting solutions also tells you whether one exists, which is why this refutes ETH.

Why I find this beautiful

First, the science. According to Science, Anthropic counted more than 800 papers that prove results only by assuming ETH or a stronger version of it. MIT's Ryan Williams points out that many of those results are not dead, but they will need to be rebuilt on safer assumptions. That is a whole field getting new questions to work on.

Second, the way it was shipped. Anthropic's repo pins Lean and Mathlib v4.33.1. You run lake build, it took them about 8 minutes on 24 virtual CPUs, and a script checks that the main theorems rely only on Lean's three standard axioms. Its CI re-checks the proofs with a second, independently written kernel. The README is refreshingly honest, too: Lean checks the proofs, "but no machine checks that this file says what the paper says", so the statement file is kept short enough for a human to read.

Third, the humility around it. OpenAI asked Impagliazzo, Paturi and Williams to examine and explain the proof, and the materials went public right away at their request. Their open letter says their involvement "should not be taken as certification of the claim", and Impagliazzo told Science he is not 100% certain yet.

Let's keep it grounded

This is not P = NP, and it won't speed up your SAT solver. Anthropic's README calls the result "purely asymptotic", and its paper estimates the approach is unlikely to beat brute force below roughly 10 million variables. The value is theoretical, and human verification is still under way, with a review conference planned before the end of the year.

Sources

What excites me most is the pattern: AI proposes, Lean checks, humans understand. I'll be following the review closely.

Reacties

Een reactie posten

Populaire posts van deze blog

Meta just shared the full recipe for a 30B agent model you can run at home 🧠

When Meta released Muse Glimmer in August, the pitch was simple: an open-weight, Apache 2.0 model built for AI agents that run on your own Mac or PC. What was missing was the "how". On 19 October, Meta Superintelligence Labs published the full technical report, and for anyone who cares about distillation and local agents, it is one of the most useful reads in a while. What the model is Muse Glimmer is a dense model of about 29.6 billion parameters, including a 1.8B perception encoder, so it reads text and images and writes text. It has a 128K+ context window and was trained on data from more than a hundred languages. The design goal was strict: everything has to fit in 32 GB of GPU memory, and a smaller 4-bit variant targets 24 GB cards. The parts I found most interesting Dense beat mixture-of-experts here. That surprised me. The team trained scaling ladders for a dense model and two MoE designs with the same memory footprint. Under a fixed memory ceiling and their compu...
Meer lezen

AI that can actually "see" a crystal 🔬

Most of the solid stuff around us, from battery materials to chips, is made of crystals: atoms stacked in neat, repeating 3D patterns. Large language models are great at reading papers about those materials, but they have never really looked at the structures themselves. A team at MIT just showed a clever way around that, and the trick is one I keep coming back to: good synthetic data. What they built The model is called CLaC, short for Contrastive Language-Crystal model, and it is described in a paper in Nature Communications by Yang Jeong Park, Mayank Kumaran, Chia-Wei Hsu, Elsa Olivetti and Ju Li. MIT News covered it on 18 October 2026. If you know CLIP, the model that taught image generators to connect pictures and words, you already get the idea. CLaC has two branches: a graph neural network that reads the 3D crystal structure, and a text encoder that reads a description. Contrastive training pulls matching structure-text pairs together in one shared space and pushes mismatche...
Meer lezen

A 35B model on a Mac mini, using just 2.9 GiB of memory 🚀

There's something special about running a capable language model on hardware you own: no API bill, no data leaving the house, just a small box on your desk doing the thinking. A paper that's currently #2 on Hugging Face's trending list takes that idea further than I expected: it runs a 35-billion-parameter model on a Mac mini at about 20 tokens per second while using under 3 GiB of memory. The trick: leave the experts on the SSD The paper is called The Other Half of the Memory Wall: Serving 35B MoEs from SSD with Trained Routing Prediction , and the system is named Edge0 . It builds on a Mixture-of-Experts (MoE) model, Qwen3.6-35B-A3B. In an MoE, each token only uses a few "experts" per layer (here 4 out of 256 in each of 40 layers), so most of the weights sit idle at any given moment. Edge0 takes that literally. The expert weights (quantized to int4) stay on the SSD and are streamed in only when needed. The clever part is a small prerouter : a tiny trained he...
Meer lezen