1 · The essentials
A way of describing computations can handle many efficiently solvable questions without handling all of them. These manuscripts examine a system that allows counting but avoids making arbitrary choices among indistinguishable objects. The main manuscript identifies a question about whether a collection of equations has a solution that can be answered efficiently but cannot be expressed in this system. The inputs are finite and come without a supplied ordering of their objects. This confirms the conjecture attributed in the source to Blass, Gurevich and Shelah, and the main result has a Lean formalization. A companion manuscript shows that adding a particular kind of supported choice lets the system express a question it could not express before. Both results concern the full counting system, not merely a version with a fixed limit on how deeply its sets can be nested.
A picture to help (an imperfect image, not to be taken literally)
As an imperfect image, imagine working with an unlabeled collection of containers: you may count them, but you cannot simply designate one of several indistinguishable containers as “the first.” The results distinguish what such a rule-bound procedure can describe from what an efficient procedure can decide, and the companion manuscript considers a particular permission to make supported choices.
Why it matters
The main result separates efficient decidability from expressibility in choiceless polynomial time with counting. Counting alone does not make this formalism sufficient for all polynomial-time queries on unordered finite structures. The companion result identifies witnessed symmetric choice as a genuine increase in expressive power.
2 · Going further
The main problem is whether choiceless polynomial time with counting captures polynomial time on unordered finite structures. Here, “captures” asks whether the formalism can express every polynomial-time query on those inputs. The main manuscript gives a negative answer using consistency of a linear system over , the field with three elements: the query asks whether the equations admit a simultaneous solution. It uses a fixed binary vocabulary and is decidable in polynomial time, yet is not expressible in the full counting formalism.
The source describes this as confirming the noncapture conjecture of Blass, Gurevich and Shelah. The stated separation strategy is to exhibit this particular efficiently decidable query and establish its nondefinability in the choiceless counting system. The supplied abstract does not describe the technical argument establishing nondefinability, so no more detailed proof mechanism can be extracted from it. The main result has a Lean formalization.
The companion manuscript addresses a different comparison: the original counting formalism versus its extension by witnessed symmetric choice. It shows in the manuscript that a fixed sentence containing just one witnessed-choice occurrence defines a Boolean query on every finite input that the original formalism cannot define. Both separations apply to the full counting formalism, allowing hereditarily finite sets of arbitrary finite rank; they are not restricted to a fixed bound on nesting depth.
Useful notions
- Finite structures with no supplied order
- Polynomial-time computation
- Expressibility in a formal language
- Consistency of linear equations
- Finite sets built from finite sets
What was known before / what is new
Before
The source identifies a noncapture conjecture of Blass, Gurevich and Shelah concerning choiceless polynomial time with counting. It supplies no further history or earlier partial results. The comparison throughout is with the full counting formalism, which allows hereditarily finite sets of arbitrary finite rank.
New
The main manuscript establishes the separation using a linear-consistency query over in a fixed binary vocabulary, and the main result has a Lean formalization. The companion manuscript shows that witnessed symmetric choice strictly increases expressive power. Its separating query is defined by a fixed sentence with one witnessed-choice occurrence.
Limits and assumptions
The polynomial-time noncapture result concerns unordered finite structures and the specified full choiceless counting formalism. The main separating query concerns linear systems over in a fixed binary vocabulary. Arbitrary finite rank is allowed, so a fixed rank restriction is not responsible for either separation. The main result is Lean-formalized; the source does not state that the companion result is formalized. The supplied abstracts give neither the technical nondefinability arguments nor a list of remaining open problems, and the companion separation alone does not establish that witnessed symmetric choice captures all of polynomial time.
Mini glossary
- Unordered finite structure —
- A finite collection of objects with specified relations but no supplied ordering of the objects.
- Polynomial time —
- A running-time bound given by a polynomial in the size of the input.
- Linear consistency —
- The property that a collection of linear equations has a simultaneous solution.
- Boolean query —
- A question whose answer on an input is yes or no.
- Expressive power —
- The range of queries that a formalism can define.
- Hereditarily finite set —
- A finite set whose members, their members, and all further levels of membership are also finite sets.
Keywords : Choiceless polynomial time · Counting · Witnessed symmetric choice
AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.
3 · Technical details and sources
Claim made in the manuscript (source text)
Confirms the Blass–Gurevich–Shelah noncapture conjecture: consistency of a linear system over 𝔽3 defines a polynomial-time query on unordered finite structures that choiceless polynomial time with counting cannot express. A separate result shows that adding witnessed symmetric choice strictly increases expressive power. Both separations hold for the full counting formalism, allowing hereditarily finite sets of arbitrary finite rank.
Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.
Manuscripts in this family
Choiceless polynomial time with counting does not capture polynomial time
23/09/2026We 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. A linear-consistency query over 𝔽3 in a fixed binary vocabulary is decidable in polynomial time but not in the full counting formalism.
Witnessed symmetric choice is strictly stronger than choiceless polynomial time with counting
24/09/2026We prove that witnessed symmetric choice strictly increases the expressive power of choiceless polynomial time with counting. 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.