A query is a property of finite relational structures that is unchanged by isomorphism. A query is in polynomial time when a deterministic algorithm decides it in time polynomial in the size of an encoding of the structure; the algorithm may use the order of the encoding, but its answer does not depend on that order. A program of choiceless polynomial time with counting (CPT) computes on the hereditarily finite sets built over the elements of the input structure as atoms, using set operations, comprehension and the cardinality operation , which returns a von Neumann ordinal, within polynomial bounds on its number of steps and on the number of objects occurring in its run; the rank of its sets is not bounded. CPT captures polynomial time when every polynomial-time query, in every fixed finite relational vocabulary, is definable by a CPT program. The question is whether CPT captures polynomial time on unordered finite structures. Let be the vocabulary of eight binary relation symbols , whose subscripts are the elements of the field . In a finite -structure , put . Put . For , put . For and , put in . The linear system of over has two separate families of unknowns, for and for , the equations for , and the equation for each such that and hold for some and . Let mean that this system is consistent.
On finite structures supplied with a linear order, Immerman and Vardi showed that first-order logic with a least fixed-point operator expresses exactly the polynomial-time queries. Blass, Gurevich and Shelah introduced choiceless polynomial time to study computation on unordered structures with hereditarily finite sets in place of arbitrary choices of an ordering. In the 1997 version of that work, they conjectured that its extension by counting is still a proper fragment of polynomial time. In early work, Shelah claimed that counting extensions of choiceless computation do not capture polynomial time. Later accounts, from Blass, Gurevich and Shelah in 2002 to Dawar, Grädel, Kullmann and Pago in 2025, continued to treat the question as open. Cai, Fürer and Immerman constructed a polynomial-time graph query that is not definable in fixed-point logic with counting.
The preprint proves that , on all finite -structures, is isomorphism-invariant and decidable in deterministic polynomial time, but not definable in CPT. This confirms the conjecture of Blass, Gurevich and Shelah. The solvability operator over adds to a logic the test whether a system of linear equations over defined by formulas is consistent. The rank operator over adds to a logic a term for the rank of a matrix over defined by formulas. The preprint also derives that neither fixed-point logic with counting extended by the solvability operator over nor fixed-point logic with counting extended by the rank operator over is contained in CPT, a consequence that is not in the Lean library.
The Lean library Choiceless proves this theorem. Lean has checked every result of the Lean library, so the Lean library is the reference: the results on these pages are stated as the Lean library states them, each linked to the Lean declaration behind it, and where the preprint states a result differently, its statement is given beside the Lean library’s. The preprint is a guide only, giving the results their order and their names.
Choiceless is a Lean library: 34 items, in eight groups. Each has a page written by OctoInform, listed below.
No item matches.