Search

Separating choiceless counting from polynomial time and witnessed choice

Claims a polynomial-time query that choiceless polynomial time with counting cannot express.

2 papers September 23, 2026 Explained by AI

Some logics try to describe every fast computation on data that comes without a built-in order. Choiceless polynomial time with counting was a leading candidate. The first paper gives a question about linear equations mod 3 that a fast algorithm answers but this logic cannot. The second shows that adding one certified choice step makes the logic strictly stronger. Lean proofs check both main theorems.

First step
1999
Andreas Blass, Yuri Gurevich and Saharon Shelah, choiceless polynomial time
Significance
Major
It settles a long-standing candidate in the search for a logic of polynomial time.
Trust
Formal proof listed
Field
Mathematical logic
2 papers

The explanation

Here is the kind of equation system at the centre of the first paper. Work with numbers modulo 3, so 3 counts as 0. Draw a triangle with corners A, B and C. Put an unknown flow on each side: x from A to B, y from B to C, z from C to A. At each corner, outflow minus inflow must equal a given charge. So x − z = c_A, y − x = c_B and z − y = c_C. Add the three equations. The left side cancels to 0. So the charges must add up to 0 for a solution to exist. With charges 0, 0, 0, setting x = y = z works. With charges 1, 0, 0, the sum is 1 and there is no solution.

A query is a yes-or-no property of finite structures that does not change when you rename the elements. Gaussian elimination, the school method for solving linear equations, decides systems like this quickly. But it needs an order on the unknowns. Descriptive complexity asks which logics can express every polynomial-time query without first choosing an order. Choiceless polynomial time with counting, CPT, works with nested finite sets built from the input. It may count, but it never picks an element arbitrarily. Blass, Gurevich and Shelah conjectured in 1997 that CPT still misses some polynomial-time queries. Shelah's early work also claimed this, and later accounts still called the question open. The paper gives a separate proof that does not rely on Shelah's claim.

The first paper claims that CPT does not capture polynomial time, confirming that conjecture. Its query asks whether a linear system modulo 3 is consistent. It is decidable in polynomial time but not in CPT. For each grid size L, the paper builds two three-dimensional grid structures. One has all charges zero and one has a single charge equal to one, so the query answers differ. The obstacle is that CPT may build sets of any nesting depth. The paper shows every symmetric enough set it builds is pinned down by a short list of atoms. That bound does not depend on the nesting depth. Then any fixed CPT program gives the same answer on both grids once L is large enough.

The second paper adds witnessed symmetric choice. That operation picks an element of a set only while building symmetries that prove the choice cannot matter. The paper claims one such choice, used once in a fixed sentence, defines a query that no CPT sentence defines. This answers a question posed by Lichter and Schweitzer.

How sure is this? A computer proof checker called Lean has formal proofs of both main theorems. One covers the explicit query with eight relations that is decidable in polynomial time but not definable in CPT. The other covers the fixed sentence with one witnessed-choice step. The first paper's corollary about two linear-algebra logics is not listed in the Lean scope. No specialist review of either paper has been published.

What it doesn't show. This does not find a logic that captures polynomial time, or settle how nested witnessed-choice operators behave.

Where it came from

This result comes from an unreleased OpenAI model, published in the openai/math release on 6 October 2026.

Hype check

Both main theorems have Lean proofs. They answer open questions in descriptive complexity, but they do not find a logic for polynomial time. No specialist review is published.

Words used

Query
A yes-or-no property of finite structures that stays the same when elements are renamed.
Polynomial time
Solvable by an algorithm whose running time grows at most like a fixed power of the input size.
Choiceless polynomial time with counting (CPT)
A logic that computes with nested finite sets over the input, can count, but never picks an element arbitrarily.
Captures polynomial time
Every isomorphism-invariant polynomial-time query can be written in the logic.
Witnessed symmetric choice
An operation that may pick one element of a set, but only while building symmetries showing the pick does not change the answer.
Modulo 3
Arithmetic where only remainders after division by 3 count, so 3 equals 0.

The original papers (2)

Lean notes

All quoted lines (10)
  1. Their original 1997 preprint explicitly conjectured that the extension by counting is still a proper fragment of polynomial time.
    Choiceless polynomial time with counting does not capture polynomial time Back to text
  2. We give a separate proof for the explicit query above; Shelah's claim is not a theorem input to this argument.
    Choiceless polynomial time with counting does not capture polynomial time Back to text
  3. We prove that choiceless polynomial time with counting does not capture polynomial time on unordered finite structures, confirming the noncapture conjecture of Blass, Gurevich and Shelah.
    Choiceless polynomial time with counting does not capture polynomial time Back to text
  4. A linear-consistency query over F3\mathbb F_3 in a fixed binary vocabulary is decidable in polynomial time but not in the full counting formalism.
    Choiceless polynomial time with counting does not capture polynomial time Back to text
  5. The all-zero configurations give a solution in the zero-charge structure, so the query has opposite answers on the pair.
    Choiceless polynomial time with counting does not capture polynomial time Back to text
  6. The bound does not depend on the object's rank.
    Choiceless polynomial time with counting does not capture polynomial time Back to text
  7. Counting equivalence forces the same halt stage and output on the two structures, contradicting their opposite query answers.
    Choiceless polynomial time with counting does not capture polynomial time Back to text
  8. Witnessed symmetric choice allows a more specific operation: select an element of an orbit while constructing automorphisms that certify the permitted symmetry.
    Witnessed symmetric choice is strictly stronger than choiceless polynomial time with counting Back to text
  9. A fixed sentence with one witnessed-choice occurrence defines a Boolean query on every finite input that is not definable in the original counting formalism.
    Witnessed symmetric choice is strictly stronger than choiceless polynomial time with counting Back to text
  10. In the true-model sense above, this answers affirmatively the expressiveness question posed in Section 7 of.
    Witnessed symmetric choice is strictly stronger than choiceless polynomial time with counting Back to text

Other sources

  1. openai/math, Lean scope note for family 243 The formalized result separates polynomial time from choiceless polynomial time with counting.
  2. openai/math release notes (2026): model provenance and review status manuscripts and supporting proof artifacts produced by an internal OpenAI model

Browse Mathematical logic Open since the 1990sLean-checked results