OctoInformBeta

OpenAI preprint, September 2026 · §1. Introduction · §1

Choiceless polynomial time with counting, and polynomial time: Programs on hereditarily finite sets over the atoms within polynomial time and space, and polynomial-time Turing machines deciding the separating query on ordered encodings

Choiceless polynomial time with counting and ordinary polynomial time.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Does choiceless polynomial time with counting (CPT) capture polynomial time? A CPT program decides a property of a finite structure by computing with sets built from its atoms, and has no order of the atoms to go by; a Turing machine reads the structure written out as a string, which lists the atoms in some order. The two are compared on structures over one vocabulary, where the separating query QQ asks whether a system of linear equations over 𝔽=𝔽3\mathbb F = \mathbb F_3, read off the structure, has a solution.

The vocabulary is τ={Ed,Cf,EB,VB,I,Z0,Z1,Z2}\tau = \{\mathrm{Ed}, \mathrm{Cf}, \mathrm{EB}, \mathrm{VB}, \mathrm{I}, \mathrm{Z}_0, \mathrm{Z}_1, \mathrm{Z}_2\}, eight binary relation symbols. An input structure 𝒜\mathcal A is a finite set AA of atoms with a binary relation R𝒜R^{\mathcal A} on AA for each R∈τR \in \tau, and a query is a property of input structures.✦ The library defines when a query is definable in CPT, through its own language of terms, rules and runs, and when QQ is decidable in polynomial time, through Turing machines reading an ordered encoding of the structure.

Hereditarily Finite Sets

The set HF(A)\mathrm{HF}(A) of hereditarily finite sets over a set AA of atoms is the least set that contains the atoms and every finite subset of itself: HF(A)=A∪{x:x a finite subset of HF(A)}.\mathrm{HF}(A) = A \cup \{\, x : x \text{ a finite subset of } \mathrm{HF}(A) \,\}.(1)✦ An atom has no elements. The transitive closure of x∈HF(A)x \in \mathrm{HF}(A) is the finite set tc(x)={x}∪⋃y∈xtc(y)\mathrm{tc}(x) = \{x\} \cup \bigcup_{y \in x} \mathrm{tc}(y)✦, and that of a finite family F⊆HF(A)F \subseteq \mathrm{HF}(A) is tc(F)=⋃x∈Ftc(x)\mathrm{tc}(F) = \bigcup_{x \in F} \mathrm{tc}(x)✦.

The von Neumann ordinal [j][j] of j∈ℕj \in \mathbb N is the set of the ordinals below it: [0]=∅,[j+1]=[j]∪{[j]}.[0] = \emptyset, \qquad [j+1] = [j] \cup \{[j]\}.(2)✦ The truth value true is 1=[1]={∅}1 = [1] = \{\emptyset\}. The cardinality operation Card\mathrm{Card} sends x∈HF(A)x \in \mathrm{HF}(A) to the ordinal of its number |x||x| of elements: Card(x)=[|x|].\mathrm{Card}(x) = [\,|x|\,].(3)✦

Terms, Rules and Programs

Fix a finite set FF of dynamic function symbols, each with an arity, and variables v0,v1,…v_0, v_1, \dots. The CPT terms over FF and τ\tau are t::=vi∣[n]∣A∣f(t1,…,tk)∣Pair(t1,t2)∣⋃t∣Unique(t)∣Card(t)∣t1=t2∣t1∈t2∣Atom(t)∣R(t1,t2)∣¬t∣t1∧t2∣t1∨t2∣if t0 then t1 else t2∣{s:vi∈r,g}\begin{aligned} t \;::=\;& v_i \mid [n] \mid A \mid f(t_1, \dots, t_k) \mid \mathrm{Pair}(t_1, t_2) \mid {\textstyle\bigcup} t \mid \mathrm{Unique}(t) \mid \mathrm{Card}(t) \mid t_1 = t_2 \mid t_1 \in t_2 \\ &\mid \mathrm{Atom}(t) \mid R(t_1, t_2) \mid \neg t \mid t_1 \wedge t_2 \mid t_1 \vee t_2 \mid \text{if } t_0 \text{ then } t_1 \text{ else } t_2 \mid \{\, s : v_i \in r,\ g \,\} \end{aligned}(4)✦ with n∈ℕn \in \mathbb N, f∈Ff \in F of arity kk and R∈τR \in \tau. Here Pair\mathrm{Pair}, ⋃\bigcup and Unique\mathrm{Unique} are pairing, union and unique element, Atom\mathrm{Atom} is the atom test, and {s:vi∈r,g}\{s : v_i \in r,\ g\} is comprehension with bound rr, guard gg and body ss. The term AA denotes the set of all atoms, the hereditarily finite set whose members are the elements of AA taken as atoms.

The CPT rules, built from updates by parallel composition, conditionals, forall and let, are Π::=skip∣f(t1,…,tk):=t∣Π1∥Π2∣if t then Π1 else Π2∣forall vi∈t do Π∣let vi=t in Π.\Pi \;::=\; \mathrm{skip} \mid f(t_1, \dots, t_k) := t \mid \Pi_1 \parallel \Pi_2 \mid \text{if } t \text{ then } \Pi_1 \text{ else } \Pi_2 \mid \text{forall } v_i \in t \text{ do } \Pi \mid \text{let } v_i = t \text{ in } \Pi.(5)✦

A CPT program PP over τ\tau is a finite set FPF_P of dynamic function symbols with their arities, together with a rule ΠP\Pi_P, its body, over FPF_P and two further symbols halt\mathrm{halt} and accept\mathrm{accept} of arity 00: P=(FP,ΠP),ΠP a rule over FP∪{halt,accept}.P = (F_P, \Pi_P), \qquad \Pi_P \text{ a rule over } F_P \cup \{\mathrm{halt}, \mathrm{accept}\}.(6)✦ A state of PP over AA is a map that gives every location (f,x‾)(f, \bar x), a symbol ff of arity kk with arguments x‾∈HF(A)k\bar x \in \mathrm{HF}(A)^k, a value in HF(A)\mathrm{HF}(A), the empty set at all but finitely many locations. The flag halt\mathrm{halt} or accept\mathrm{accept} holds in a state when its value there is 11.✦

Runs and Their Bounds

The run of PP on an input structure 𝒜\mathcal A is the sequence of states S0=Sinit,Sj+1=ΔP,𝒜(Sj),S_0 = S_{\mathrm{init}}, \qquad S_{j+1} = \Delta_{P,\mathcal A}(S_j),(7)✦ where SinitS_{\mathrm{init}} is the initial state of PP on 𝒜\mathcal A and ΔP,𝒜\Delta_{P,\mathcal A} is the map that executes the body ΠP\Pi_P once on a state over 𝒜\mathcal A; a step may be undefined, and then so are all later states.

The support of a state SS is its finite set of locations with a nonempty value✦, and its critical objects are the values and the arguments at those locations✦. The active objects Act(S)\mathrm{Act}(S) form the transitive closure of the critical objects together with AA, ∅\emptyset, 11 and the atoms.✦ The roots of a term at a state are the finitely many objects of HF(A)\mathrm{HF}(A) that its evaluation at the state constructs from the active objects. The roots of a rule collect those of the terms it evaluates: none for skip\mathrm{skip}, the arguments and the new value of an update, both parts of a parallel rule, the condition and the branch it selects, the bound and, for each element xx of its value, the body with vi=xv_i = x, and for a let the bound term and the body with viv_i set to its value.✦ The roots Roots(S)\mathrm{Roots}(S) of a step from SS are none when halt\mathrm{halt} holds in SS, and otherwise those of ΠP\Pi_P at SS with every variable set to ∅\emptyset.✦ The objects occurring in the first hh steps are Occh=⋃j≤hAct(Sj)∪⋃j<htc(Roots(Sj)),\mathrm{Occ}_h = \bigcup_{j \le h} \mathrm{Act}(S_j) \;\cup\; \bigcup_{j < h} \mathrm{tc}(\mathrm{Roots}(S_j)),(8)✦ the unions running over the defined states.

For polynomials p,qp, q with natural coefficients, PP accepts 𝒜\mathcal A within time pp and space qq when its run reaches, within p(|A|)p(|A|) steps, a state in which both flags hold, with at most q(|A|)q(|A|) objects occurring up to then: ∃h≤p(|A|):Sh defined,halt and accept hold in Sh,|Occh|≤q(|A|).\exists h \le p(|A|):\quad S_h \text{ defined},\quad \mathrm{halt} \text{ and } \mathrm{accept} \text{ hold in } S_h,\quad |\mathrm{Occ}_h| \le q(|A|).(9)✦

The Query and Its Encoding

In an input structure 𝒜\mathcal A, the configuration atoms are X={a:Cf(a,a)}X = \{a : \mathrm{Cf}(a,a)\}✦ and the edge atoms Y={y:Ed(y,y)}Y = \{y : \mathrm{Ed}(y,y)\}✦; for t∈Xt \in X let Xt={a∈X:VB(t,a)}X_t = \{a \in X : \mathrm{VB}(t,a)\}. The coefficient of y∈Yy \in Y at a∈Xa \in X is c(y,a)=∑x∈Y,I(a,x)∑δ∈𝔽,Zδ(y,x)δ,c(y,a) = \sum_{x \in Y,\ \mathrm{I}(a,x)} \ \sum_{\delta \in \mathbb F,\ \mathrm{Z}_\delta(y,x)} \delta,(10)✦ and t∈Xt \in X is incident to y∈Yy \in Y when I(a,x)\mathrm{I}(a,x) and EB(y,x)\mathrm{EB}(y,x) for some a∈Xta \in X_t and x∈Yx \in Y✦. The structure 𝒜\mathcal A satisfies the query QQ when there are weights λ:X→𝔽\lambda\colon X \to \mathbb F, normalized on every XtX_t, and μ:Y→𝔽\mu\colon Y \to \mathbb F, consistent with λ\lambda at every incident pair: ∑a∈Xtλ(a)=1(t∈X),μ(y)=∑a∈Xtλ(a)c(y,a)(t incident to y).\sum_{a \in X_t} \lambda(a) = 1 \quad (t \in X), \qquad \mu(y) = \sum_{a \in X_t} \lambda(a)\, c(y,a) \quad (t \text{ incident to } y).(11)✦

An ordered input of size NN is an input structure on {0,…,N−1}\{0, \dots, N-1\}.✦ For an input structure 𝒜\mathcal A on AA and a bijection e:A→{0,…,N−1}e\colon A \to \{0, \dots, N-1\}, the ordered copy 𝒜e\mathcal A^e is the ordered input with R𝒜e(i,j)⇔R𝒜(e−1(i),e−1(j))(R∈τ).R^{\mathcal A^e}(i,j) \iff R^{\mathcal A}(e^{-1}(i), e^{-1}(j)) \qquad (R \in \tau).(12)✦

List τ\tau as R0,…,R7=Ed,Cf,EB,VB,I,Z0,Z1,Z2R_0, \dots, R_7 = \mathrm{Ed}, \mathrm{Cf}, \mathrm{EB}, \mathrm{VB}, \mathrm{I}, \mathrm{Z}_0, \mathrm{Z}_1, \mathrm{Z}_2. The tape code of an ordered input ℬ\mathcal B of size NN is the word over the alphabet {⊥}∪𝔽\{\bot\} \cup \mathbb F that writes NN in unary, then the letter 00, then the 8N28N^2 relation bits: code(N,ℬ)=⊥N0β0β1⋯β8N2−1,βN2i+Nu+w={1if Riℬ(u,w),0otherwise.\mathrm{code}(N, \mathcal B) = \bot^N\, 0\, \beta_0 \beta_1 \cdots \beta_{8N^2-1}, \qquad \beta_{N^2 i + N u + w} = \begin{cases} 1 & \text{if } R_i^{\mathcal B}(u,w), \\ 0 & \text{otherwise.} \end{cases}(13)✦

The Definition

Definition 1. A query 𝒬\mathcal Q is definable in CPT if there are a CPT program PP over τ\tau and polynomials p,qp, q with natural coefficients such that, for every finite set AA and every input structure 𝒜\mathcal A on AA, in the sense of (9), P accepts 𝒜 within time p and space q⇔𝒜 satisfies 𝒬.P \text{ accepts } \mathcal A \text{ within time } p \text{ and space } q \iff \mathcal A \text{ satisfies } \mathcal Q.(14)✦ The query QQ of (11) is decidable in polynomial time if there are a map α\alpha from ordered inputs to {true,false}\{\mathrm{true}, \mathrm{false}\} and a multi-tape Turing machine with finite tape alphabets that computes α\alpha in polynomial time, reading code(N,ℬ)\mathrm{code}(N, \mathcal B) of (13) and writing the one-letter word 11 for true and 00 for false, such that for every finite set AA, every N∈ℕN \in \mathbb N, every bijection e:A→{0,…,N−1}e\colon A \to \{0, \dots, N-1\} and every input structure 𝒜\mathcal A on AA, α(N,𝒜e)=true⇔𝒜 satisfies Q.\alpha(N, \mathcal A^e) = \mathrm{true} \iff \mathcal A \text{ satisfies } Q.(15)✦

In the paper, the definitions read: CPT computes on the hereditarily finite sets over the input atoms with set operations, comprehension and the cardinality operation Card\mathrm{Card}, which returns a von Neumann ordinal, under polynomial bounds on the computation and on the number of recursively occurring objects, and polynomial time means decidability by a deterministic algorithm, polynomial in an ordered encoding, whose answer does not depend on the order.

What Is Checked

Definability in CPT (14) is stated over input structures on finite sets of atoms, CPT programs over τ\tau with their runs (7) and occurring objects (8), and polynomials with natural coefficients; polynomial time for QQ (15) is stated over the same structures, their ordered copies (12), and multi-tape Turing machines with finite alphabets reading the tape code (13).