OctoInformBeta

Separating choiceless counting from polynomial time and witnessed choice

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 𝖢𝖺𝗋𝖽\mathsf{Card}, 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 τ\tau be the vocabulary of eight binary relation symbols 𝖤𝖽,𝖢𝖿,𝖤𝖡,𝖵𝖡,𝖨,𝖹0,𝖹1,𝖹2\mathsf{Ed},\mathsf{Cf},\mathsf{EB},\mathsf{VB},\mathsf I,\mathsf Z_0,\mathsf Z_1,\mathsf Z_2, whose subscripts are the elements of the field 𝔽3\mathbb F_3. In a finite τ\tau-structure AA, put Y={y∈A:𝖤𝖽(y,y)}Y=\{y\in A:\mathsf{Ed}(y,y)\}. Put X={a∈A:𝖢𝖿(a,a)}X=\{a\in A:\mathsf{Cf}(a,a)\}. For t∈Xt\in X, put Xt={a∈X:𝖵𝖡(t,a)}X_t=\{a\in X:\mathsf{VB}(t,a)\}. For y∈Yy\in Y and a∈Xa\in X, put C(y,a)=∑x∈Y,𝖨(a,x)∑δ∈𝔽3,𝖹δ(y,x)δC(y,a)=\sum_{x\in Y,\ \mathsf I(a,x)}\ \sum_{\delta\in\mathbb F_3,\ \mathsf Z_\delta(y,x)}\delta in 𝔽3\mathbb F_3. The linear system of AA over 𝔽3\mathbb F_3 has two separate families of unknowns, λa\lambda_a for a∈Xa\in X and μy\mu_y for y∈Yy\in Y, the equations ∑a∈Xtλa=1\sum_{a\in X_t}\lambda_a=1 for t∈Xt\in X, and the equation μy=∑a∈XtλaC(y,a)\mu_y=\sum_{a\in X_t}\lambda_a C(y,a) for each (t,y)∈X×Y(t,y)\in X\times Y such that 𝖨(a,x)\mathsf I(a,x) and 𝖤𝖡(y,x)\mathsf{EB}(y,x) hold for some a∈Xta\in X_t and x∈Yx\in Y. Let Q(A)Q(A) 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 QQ, on all finite τ\tau-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 𝔽3\mathbb F_3 adds to a logic the test whether a system of linear equations over 𝔽3\mathbb F_3 defined by formulas is consistent. The rank operator over 𝔽3\mathbb F_3 adds to a logic a term for the rank of a matrix over 𝔽3\mathbb F_3 defined by formulas. The preprint also derives that neither fixed-point logic with counting extended by the solvability operator over 𝔽3\mathbb F_3 nor fixed-point logic with counting extended by the rank operator over 𝔽3\mathbb F_3 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.

The Lean library: Choiceless

Choiceless is a Lean library: 34 items, in eight groups. Each has a page written by OctoInform, listed below.

§1. Introduction 4 items
  1. The separating query Q The separating query asks for consistent weights over 𝔽3\mathbb{F}_3. §1
  2. Choiceless polynomial time with counting, and polynomial time Choiceless polynomial time with counting and ordinary polynomial time. §1
  3. Theorem 1 An isomorphism-invariant polynomial-time query outside choiceless polynomial time.
  4. Proposition 2 The separating query is a polynomial-time query.
§2. The grid structures 4 items
  1. The box grid, face cycles and edge groups The box grid, its face cycles and its edge groups. §2
  2. The structures A_b The grid structure of a charge on the cubic grid. §2
  3. Lemma 4 Grid structures of side at least two have charge-independent size.
  4. Proposition 5 For L≥2L \ge 2, QQ separates zero charge from a point charge.
§3. Small orbits have sparse supports 5 items
  1. The central extension H, its central flows K, and K-supports The central extension by grid flows, and hereditarily supported sets. §3
  2. Lemma 6 The box group acts on each grid structure by automorphisms.
  3. Lemma 7 An edge labelling with sparse curl is nearly a gradient.
  4. Proposition 8 Objects with small orbits are supported by few atoms.
  5. Corollary 9 Small invariant, membership-transitive families have short supports.
§4. Counting equivalence and homogeneity 6 items
  1. The analysis expansion Ā_b and the counting logic C^h The analysis expansion of the grid structure and counting types. §4
  2. Lemma 10 An isoperimetric inequality for the cubic grid.
  3. The giant component Deleting few grid edges leaves a giant component. §4
  4. Proposition 11 On large grids no counting sentence separates the two charges.
  5. Lemma 12 When values on some edges extend to a flow over 𝔽3\mathbb{F}_3.
  6. Proposition 13 Counting types of short grid tuples determine their flow orbit.
§5. From atom types to hereditarily finite sets 7 items
  1. Theorem 14 Transfer of counting equivalence to hereditarily supported sets.
  2. Lemma 15 Equal CMC^M types have equally many extensions of each type.
  3. Molecules and forms Forms turn types of atom tuples into hereditarily finite sets. §5
  4. Lemma 16 Values of forms are hereditarily supported and equivariant.
  5. Lemma 17 Counting types determine the atomic facts of form values.
  6. Lemma 18 A bijection that keeps assignments represented alike.
  7. Proof of Theorem 14: induction on formulas Assignments represented alike satisfy the same counting formulas. §5
§6. Encoding complete choiceless computations 5 items
  1. Interpretation programs Programs that iterate logical interpretations with the Härtig quantifier. §6
  2. The hereditary encoding Hereditarily finite codes for the states of interpretation programs. §6
  3. Lemma 19 A bounded interpretation program leaves a small invariant trace.
  4. Lemma 20 Counting logic defines coded program states below a step bound.
  5. Lemma 21 Program formulas translate into counting logic with mm names.
§7. Proof of the separation 1 item
  1. Proof of Theorem 1: fixing the parameters and comparing the runs No choiceless machine with polynomial bounds decides the separating query. §7
The direct lower bound for the BGS-style language (no numbered counterpart) 2 items
  1. Operational machines, and Lemmas 19 and 20 for machine states Programs and their compiled machines accept within the same bounds.
  2. The direct lower bound and its variants No choiceless polynomial time program with counting decides the Gauss query.

No item matches.