OpenAI maakte op 26 oktober 2026 bekend dat een intern systeem een resultaat had opgeleverd dat volgens het bedrijf de Exponential Time Hypothesis (ETH) weerlegt. Die hypothese gaat over de slechtst mogelijke rekentijd van booleaanse vervulbaarheidsproblemen. OpenAI dateert de uitgeschreven redenering op 16 oktober en de formalisering in Lean op 17 oktober.
OpenAI kondigde een externe groep aan die het resultaat zou beoordelen en toelichten. Die groep wordt geleid door Russell Impagliazzo, Ramamohan Paturi en Ryan Williams.
Wat de Lean-documentatie formaliseert
De Lean-scopepagina beschrijft een deterministische machine die het aantal oplossingen exact telt voor canoniek gecodeerde k-CNF-formules, met een vaste k van minstens 2. Een oplossing is hier een toekenning van waarden aan de variabelen die de formule waar maakt.
Voor die berekening noemt de documentatie een looptijd van (L+1)^{O_k(1)} 2^{O_k(n(log log n)^2/√log n)}. Daarbij is L de bitlengte van de codering en n het aantal variabelen. Dezelfde scope stelt dat de machine per stap in totaal hoogstens (L+1)^{O_k(1)} tapevakken heeft bezocht.
De scherpere manuscriptgrens is een aparte uitspraak
De Lean-scopepagina schrijft een scherpere looptijd toe aan het begeleidende manuscript: (n+m)^{O_k(1)} 2^{O_k(n log log n/√log n)}, waarbij m het aantal clausules is. Voor m ≤ Dn, met een vaste D > 0, noemt de pagina bovendien (n+m)^{O_{k,D}(1)} 2^{O_{k,D}(n/√log n)}.
Die twee looptijdgrenzen zijn dus uitspraken over het manuscript, naast de grens van de geformaliseerde Lean-stelling. De scherpere grenzen zijn niet de looptijd die de Lean-scope zelf voor die stelling geeft.
Wat dit zegt over ETH en praktische software
OpenAI presenteerde zijn resultaat als een claim over ETH en kondigde geen oplossing van P versus NP aan. Het bedrijf zegt dat aanzienlijk vervolgonderzoek nodig is om theoretische vooruitgang om te zetten in praktische verbeteringen. De gemelde grenzen leveren op zichzelf dus geen directe versnelling van computers of SAT-software op.
Op 28 oktober 2026 meldde ExplainX dat er tot die dag geen onafhankelijke bevestiging van het resultaat was gerapporteerd.
