# Separating choiceless counting from polynomial time and witnessed choice

> Claims a polynomial-time query that choiceless polynomial time with counting cannot express. Plain-English explainer, Lean status and sources.

Canonical: https://closedform.nishachay.tech/e/openai-math-2026-243/
Last updated: 2026-10-14

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

**Trust:** Formal proof listed · **Papers:** 2 · **First paper:** September 23, 2026 · **Field:** Mathematical logic · **Entry:** 243

*Explained by AI.* Drafted by one AI model and checked sentence by sentence against the paper by a different one. Spot a mistake? Report an error.

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.

## At a glance

- **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[1]. 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[2].

The first paper claims that CPT does not capture polynomial time, confirming that conjecture[3]. Its query asks whether a linear system modulo 3 is consistent. It is decidable in polynomial time but not in CPT[4]. 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[5]. 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[6]. Then any fixed CPT program gives the same answer on both grids once L is large enough[7].

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[8]. The paper claims one such choice, used once in a fixed sentence, defines a query that no CPT sentence defines[9]. This answers a question posed by Lichter and Schweitzer[10].

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)

- [Choiceless polynomial time with counting does not capture polynomial time](https://github.com/openai/math/blob/main/preprints/Choiceless-polynomial-time-with-counting-does-not-capture-polynomial-time-September-23-2026/paper.pdf) - September 23, 2026 · Formal proof listed
- [Witnessed symmetric choice is strictly stronger than choiceless polynomial time with counting](https://github.com/openai/math/blob/main/preprints/Witnessed-symmetric-choice-is-strictly-stronger-than-choiceless-polynomial-time-with-counting-September-24-2026/paper.pdf) - September 24, 2026

- [Lean notes](https://github.com/openai/math/blob/main/lean/docs/243.md)

## Quoted lines from the paper (10)

[1] From [Choiceless polynomial time with counting does not capture polynomial time](https://github.com/openai/math/blob/main/preprints/Choiceless-polynomial-time-with-counting-does-not-capture-polynomial-time-September-23-2026/paper.pdf):

> Their original 1997 preprint explicitly conjectured that the extension by counting is still a proper fragment of polynomial time.

[2] From [Choiceless polynomial time with counting does not capture polynomial time](https://github.com/openai/math/blob/main/preprints/Choiceless-polynomial-time-with-counting-does-not-capture-polynomial-time-September-23-2026/paper.pdf):

> We give a separate proof for the explicit query above; Shelah's claim is not a theorem input to this argument.

[3] From [Choiceless polynomial time with counting does not capture polynomial time](https://github.com/openai/math/blob/main/preprints/Choiceless-polynomial-time-with-counting-does-not-capture-polynomial-time-September-23-2026/paper.pdf):

> 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.

[4] From [Choiceless polynomial time with counting does not capture polynomial time](https://github.com/openai/math/blob/main/preprints/Choiceless-polynomial-time-with-counting-does-not-capture-polynomial-time-September-23-2026/paper.pdf):

> A linear-consistency query over $\mathbb F_3$ in a fixed binary vocabulary is decidable in polynomial time but not in the full counting formalism.

[5] From [Choiceless polynomial time with counting does not capture polynomial time](https://github.com/openai/math/blob/main/preprints/Choiceless-polynomial-time-with-counting-does-not-capture-polynomial-time-September-23-2026/paper.pdf):

> The all-zero configurations give a solution in the zero-charge structure, so the query has opposite answers on the pair.

[6] From [Choiceless polynomial time with counting does not capture polynomial time](https://github.com/openai/math/blob/main/preprints/Choiceless-polynomial-time-with-counting-does-not-capture-polynomial-time-September-23-2026/paper.pdf):

> The bound does not depend on the object's rank.

[7] From [Choiceless polynomial time with counting does not capture polynomial time](https://github.com/openai/math/blob/main/preprints/Choiceless-polynomial-time-with-counting-does-not-capture-polynomial-time-September-23-2026/paper.pdf):

> Counting equivalence forces the same halt stage and output on the two structures, contradicting their opposite query answers.

[8] From [Witnessed symmetric choice is strictly stronger than choiceless polynomial time with counting](https://github.com/openai/math/blob/main/preprints/Witnessed-symmetric-choice-is-strictly-stronger-than-choiceless-polynomial-time-with-counting-September-24-2026/paper.pdf):

> Witnessed symmetric choice allows a more specific operation: select an element of an orbit while constructing automorphisms that certify the permitted symmetry.

[9] From [Witnessed symmetric choice is strictly stronger than choiceless polynomial time with counting](https://github.com/openai/math/blob/main/preprints/Witnessed-symmetric-choice-is-strictly-stronger-than-choiceless-polynomial-time-with-counting-September-24-2026/paper.pdf):

> 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.

[10] From [Witnessed symmetric choice is strictly stronger than choiceless polynomial time with counting](https://github.com/openai/math/blob/main/preprints/Witnessed-symmetric-choice-is-strictly-stronger-than-choiceless-polynomial-time-with-counting-September-24-2026/paper.pdf):

> In the true-model sense above, this answers affirmatively the expressiveness question posed in Section 7 of.

## Other sources

- [openai/math, Lean scope note for family 243](https://github.com/openai/math/blob/main/lean/docs/243.md): “The formalized result separates polynomial time from choiceless polynomial time with counting.”
- [openai/math release notes (2026): model provenance and review status](https://github.com/openai/math/blob/main/README.md): “manuscripts and supporting proof artifacts produced by an internal OpenAI model”

## Related

- [Weak normalization implies strong normalization in pure type systems](https://closedform.nishachay.tech/e/openai-math-2026-245/) - Mathematical logic
- [Single-fold Diophantine representations and undecidability under an at-most-one-solution promise](https://closedform.nishachay.tech/e/openai-math-2026-242/) - Mathematical logic
- [The Partition Principle does not imply Choice](https://closedform.nishachay.tech/e/openai-math-2026-244/) - Mathematical logic
- [Rigidity of the Turing degrees](https://closedform.nishachay.tech/e/openai-math-2026-241/) - Mathematical logic
- [Shelah's eventual categoricity and the prescribed-threshold obstruction](https://closedform.nishachay.tech/e/openai-math-2026-240/) - Mathematical logic
- [Mathematical logic](https://closedform.nishachay.tech/science/mathematics/mathematical-logic/) - Field · 6 results
- [Open since the 1990s](https://closedform.nishachay.tech/open-since/1990s/) - Era · 55 results
- [Lean-checked results](https://closedform.nishachay.tech/trust/lean-checked/) - Trust · 242 results
- [Report an error](https://github.com/nishachay/closed-form/issues/new?template=report-error.yml&labels=entry-error&title=%5Bentry%20243%5D%20)