VibeMathedMath problems solved with AI
Sign in

The Blass-Gurevich-Shelah conjecture: choiceless polynomial time with counting does not capture polynomial time

Immerman and Vardi showed that fixed-point logic captures polynomial time on ordered finite structures; Chandra-Harel and Gurevich asked whether some logic captures polynomial time on unordered structures, and Gurevich conjectured not. Blass, Gurevich and Shelah introduced choiceless polynomial time (CPT), which computes with hereditarily finite sets over the input atoms under polynomial resource bounds without arbitrary choices, and its extension by a cardinality operation. CPT with counting was long the most prominent candidate logic for polynomial time: it defines the Cai-Furer-Immerman queries that defeat fixed-point logic with counting. Blass, Gurevich and Shelah conjectured in their 1997 preprint that the counting extension is still a proper fragment of polynomial time. Is there a polynomial-time, isomorphism-invariant query on finite structures that CPT with counting cannot define?

Result
Proved(see note)
Status
Candidate (review pending)
AI contribution
AI-discovered
Method
Argument
Field
Finite model theory; descriptive complexity
Posed by
Andreas Blass, Yuri Gurevich and Saharon Shelah
Year posed
1997
Years open
29y
Solved
2026-09-23
Model
Unreleased internal OpenAI model
Vendor
OpenAI
Collaborators
—
Verification
Lean-checked, statement unaudited
Publication
Announced
Collection
OpenAI math release (October 2026), version adc7f12
Significance
42 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What was actually shown

Main theorem: over a fixed vocabulary of eight binary relations, consistency over F3\mathbb F_3 of an explicitly defined linear system (normalisation equations ∑a∈Xtλa=1\sum_{a\in X_t}\lambda_a=1 and consistency equations μy=∑a∈XtλaC(y,a)\mu_y=\sum_{a\in X_t}\lambda_aC(y,a)) is a polynomial-time query on all finite structures, with no promise, that no CPT program with counting defines, allowing hereditarily finite sets of unbounded rank. Priority: Shelah (2000) claimed noncapture for counting extensions of choiceless computation; later accounts kept the problem open, and the manuscript gives a separate proof not relying on that claim. Not shown: Gurevich's conjecture that no logic captures polynomial time, or anything about rank-based or other extensions.

What the AI did

The release README says the vast majority of results were obtained with one fixed procedure using an unreleased internal OpenAI model, on average about three hours of ChatGPT Pro thinking compute per result, and that some outputs build on earlier results produced by the models. This result is not among the README's exceptions (the Hodge conjecture for CM abelian varieties and the Re(s) > 11/12 zero-free region, whose write-up was human edited). The manuscripts are authored 'OpenAI' and name no human author. This entry's principal manuscript is dated September 23, 2026; a companion (September 24) proves a separate separation for witnessed symmetric choice (its own entry). Both have Lean formalizations of their main theorems.

Verification

No independent mathematician has checked this yet. Checked here: the main theorem was read against the Blass-Gurevich-Shelah conjecture. Lean: formalization.yaml lists OAI.CPTSeparation.main (lean/OAI/ModelTheory/Choiceless/Separation.lean, comparator ChoicelessPolynomialTime.json). Its statement was read here: the linear-consistency query is isomorphism invariant, is computed by a polynomial-time finite-alphabet Turing machine on every ordered encoding, and is not definable in the formalised hereditarily-finite-set language with cardinality and polynomial bounds on stages and objects. This is the headline claim, but it rests on the challenge file's own encoding of CPT with counting (about 550 lines), whose fidelity to the Blass-Gurevich-Shelah definition was not audited here. Not rebuilt here.

Sources

Changelog1 change

Discussion