OctoInformBeta

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

Theorem 1: QQ asks whether a linear system over 𝔽3\mathbb{F}_3 read off the input is solvable; no polynomially bounded interpretation program decides it either

An isomorphism-invariant polynomial-time query outside choiceless 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

Choiceless polynomial time with counting (CPT), the logic of Blass, Gurevich and Shelah, computes on a finite structure by building hereditarily finite sets over its elements, in parallel and without choosing among them, under polynomial bounds on the number of steps and on the number of objects that occur in the run. The question is whether CPT defines every isomorphism-invariant query that is decidable in polynomial time.

Theorem 1 answers it with an explicit query QQ from linear algebra over 𝔽=𝔽3\mathbb F = \mathbb F_3, posed on finite structures for the vocabulary Ο„={Ed,Cf,EB,VB,I,Z0,Z1,Z2}\tau = \{\mathrm{Ed}, \mathrm{Cf}, \mathrm{EB}, \mathrm{VB}, \mathrm{I}, Z_0, Z_1, Z_2\} of eight binary relation symbols, one ZΞ΄Z_\delta for each Ξ΄βˆˆπ”½\delta \in \mathbb F. Besides CPT programs, it concerns interpretation programs, which iterate a two-dimensional interpretation in first-order logic with the HΓ€rtig quantifier under a polynomial bound.

Inputs and the Query

An input SS over a finite set AA is a Ο„\tau-structure with universe AA, that is, a binary relation RSβŠ†AΓ—AR^S \subseteq A \times A for each RβˆˆΟ„R \in \tau; the elements of AA are its atoms.✦ An isomorphism from an input SS over AA to an input TT over BB is a bijection Ο€:Aβ†’B\pi\colon A \to B with RT(Ο€x,Ο€y)⇔RS(x,y)R^T(\pi x, \pi y) \iff R^S(x,y) for all RβˆˆΟ„R \in \tau and x,y∈Ax, y \in A, and Sβ‰…TS \cong T when there is one.✦

The edge atoms of SS form the set Y={y:Ed(y,y)}Y = \{y : \mathrm{Ed}(y,y)\}✦ and its configuration atoms the set X={a:Cf(a,a)}X = \{a : \mathrm{Cf}(a,a)\}✦; the block of t∈Xt \in X is Xt={a∈X:VB(t,a)}X_t = \{a \in X : \mathrm{VB}(t,a)\}. A configuration atom tt and an edge atom yy are incident when I(a,x)\mathrm{I}(a,x) and EB(y,x)\mathrm{EB}(y,x) hold for some a∈Xta \in X_t and some x∈Yx \in Y.✦ The coefficient of a configuration atom aa at an edge atom yy is the element 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,\ Z_\delta(y,x)} \delta(1)✦ of 𝔽\mathbb F.

A weighting Ξ»:X→𝔽\lambda\colon X \to \mathbb F is normalized when βˆ‘a∈XtΞ»(a)=1for every t∈X,\sum_{a \in X_t} \lambda(a) = 1 \qquad \text{for every } t \in X,(2)✦ and a labelling ΞΌ:Y→𝔽\mu\colon Y \to \mathbb F is consistent with Ξ»\lambda when, with the coefficients (1), ΞΌ(y)=βˆ‘a∈XtΞ»(a)c(y,a)for every t∈X and every y∈Y incident with t.\mu(y) = \sum_{a \in X_t} \lambda(a)\, c(y,a) \qquad \text{for every } t \in X \text{ and every } y \in Y \text{ incident with } t.(3)✦ The separating query QQ holds of SS when the linear system (2), (3) in the unknowns Ξ»(a)\lambda(a) for a∈Xa \in X and ΞΌ(y)\mu(y) for y∈Yy \in Y has a solution over 𝔽\mathbb F.✦

Polynomial Time

An ordered input of size NN is an input over {0,1,…,Nβˆ’1}\{0, 1, \dots, N-1\}.✦ The ordered copy of an input SS over AA along a bijection e:Aβ†’{0,…,Nβˆ’1}e\colon A \to \{0, \dots, N-1\} is the ordered input SeS^e with RSe(i,j)⇔RS(eβˆ’1(i),eβˆ’1(j))R^{S^e}(i,j) \iff R^S(e^{-1}(i), e^{-1}(j)) for every RβˆˆΟ„R \in \tau.✦

Write R0,…,R7R_0, \dots, R_7 for Ed,Cf,EB,VB,I,Z0,Z1,Z2\mathrm{Ed}, \mathrm{Cf}, \mathrm{EB}, \mathrm{VB}, \mathrm{I}, Z_0, Z_1, Z_2. The table of an ordered input of size NN is the string of its 8N28N^2 bits Ri(j,k)R_i(j,k) for i<8i < 8 and j,k<Nj, k < N, in lexicographic order of (i,j,k)(i,j,k).✦ The tape code of an ordered input SS of size NN is the word over the alphabet 𝔽βˆͺ{βŠ”}\mathbb F \cup \{\sqcup\} made of NN blanks βŠ”\sqcup, the letter 00, and the table of SS with each bit written as the letter 11 or 00.✦ A Boolean answer is written as the one letter 11 or 00.✦

The query QQ is decided in polynomial time, written Q∈PTIMEQ \in \mathrm{PTIME}, when there are a Boolean function gg on ordered inputs of all sizes and a Turing machine with finitely many stacks over finite alphabets that computes gg, from tape codes to answers, in time polynomial in the length of the tape code, such that g(Se)=1⇔Q(S)g(S^e) = 1 \iff Q(S)(4)✦ for every input SS over a finite set AA and every bijection ee of AA with some {0,…,Nβˆ’1}\{0, \dots, N-1\}.

Hereditarily Finite Sets

For a finite set AA of atoms, HF(A)\mathrm{HF}(A) is the set of hereditarily finite objects over AA: the least set that contains the atoms and every finite subset of itself, an atom having no elements.✦ The rank rk(x)\mathrm{rk}(x) of an object xx is 00 when xx is an atom or βŒ€\varnothing, and max⁡y∈x(rk(y)+1)\max_{y \in x}(\mathrm{rk}(y) + 1) otherwise.✦ The transitive closure of an object xx is the finite set tc(x)={x}βˆͺ⋃y∈xtc(y),\mathrm{tc}(x) = \{x\} \cup \bigcup_{y \in x} \mathrm{tc}(y),(5)✦ and that of a finite set FF of objects is tc(F)=⋃x∈Ftc(x)\mathrm{tc}(F) = \bigcup_{x \in F}\mathrm{tc}(x).✦ The von Neumann ordinals are [0]=βŒ€[0] = \varnothing and [j+1]=[j]βˆͺ{[j]}[j+1] = [j] \cup \{[j]\}✦, the truth value is [1]={βŒ€}[1] = \{\varnothing\}✦, and the set AA of all atoms is itself an object of HF(A)\mathrm{HF}(A).✦

CPT Programs

A CPT program Ξ \Pi over Ο„\tau consists of a finite set of dynamic function symbols, each with an arity, and one rule, its body, over these symbols and the two nullary control symbols halt\mathrm{halt} and accept\mathrm{accept}.✦ The terms of Ξ \Pi are built from variables, the ordinals [j][j] and the set of atoms by application f(u1,…,uk)f(u_1, \dots, u_k) of a symbol of arity kk, pairing, union, the unique-element operation, cardinality, equality, membership, the atom test, the input relations R(u,v)R(u,v) for RβˆˆΟ„R \in \tau, negation, conjunction, disjunction, conditional terms and comprehension terms {u:x∈v,w}\{u : x \in v,\ w\}, where xx is a variable and uu, vv, ww, u1,…,uku_1, \dots, u_k are terms.✦ The rules of Ξ \Pi are built from skip\mathrm{skip} and updates f(u1,…,uk):=uf(u_1, \dots, u_k) := u by parallel composition, conditional rules, parallel iteration forallx∈udoρ\mathrm{forall}\ x \in u\ \mathrm{do}\ \rho and local definitions letx=uinρ\mathrm{let}\ x = u\ \mathrm{in}\ \rho.

On an input SS over AA, a location is a symbol ff of arity kk, dynamic or control, with an argument tuple in HF(A)k\mathrm{HF}(A)^k✦, and a state ss assigns to every location a value in HF(A)\mathrm{HF}(A), all but finitely many values being βŒ€\varnothing.✦ The support of ss is the set of locations whose value is not βŒ€\varnothing✦, its critical objects Crit(s)\mathrm{Crit}(s) are the values and the arguments of the locations in the support✦, and its active objects, with tc\mathrm{tc} as in (5), are Act(s)=tc(Crit(s)βˆͺ{A,βŒ€,[1]}βˆͺA).\mathrm{Act}(s) = \mathrm{tc}\bigl(\mathrm{Crit}(s) \cup \{A, \varnothing, [1]\} \cup A\bigr).(6)✦ A control symbol holds in ss when its value is [1][1].✦

The initial state of Ξ \Pi on SS is the state in which every location has value βŒ€\varnothing. The run of Ξ \Pi on SS is the sequence of states s0,s1,…s_0, s_1, \dots that starts from the initial state, sj+1s_{j+1} being the result of firing the body in sjs_j as long as that step is defined.✦ The roots Roots(sj)\mathrm{Roots}(s_j) of the step from sjs_j are the values of the terms the body evaluates in sjs_j, along the branch each conditional takes and for every element of the range of each parallel iteration; there are none when halt\mathrm{halt} holds in sjs_j.✦ With Act\mathrm{Act} as in (6), the objects occurring up to step hh 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}\bigl(\mathrm{Roots}(s_j)\bigr),(7)✦ both unions running over the defined states.

For polynomials pp and qq with coefficients in β„•\mathbb N, Ξ \Pi accepts SS within (p,q)(p,q) when for some h≀p(|A|)h \le p(|A|) the state shs_h is defined, halt\mathrm{halt} and accept\mathrm{accept} hold in it, and the set (7) has at most q(|A|)q(|A|) elements.✦ A query on inputs is CPT-definable when some CPT program Ξ \Pi over Ο„\tau and polynomials p,qp, q are such that, for every input SS over a finite set, Ξ \Pi accepts SS within (p,q)(p,q) exactly when SS satisfies the query; for QQ this is written Q∈CPTQ \in \mathrm{CPT}.✦

Interpretation Programs

For a set Οƒ\sigma of binary relation symbols, a finite Οƒ\sigma-structure 𝔄\mathfrak A is a finite set AA, its universe, with a binary relation R𝔄R^{\mathfrak A} on AA for each RβˆˆΟƒR \in \sigma.✦ The formulas of first-order logic with the HΓ€rtig quantifier over Οƒ\sigma are built from βŠ₯\bot, x=yx = y and R(x,y)R(x,y) for RβˆˆΟƒR \in \sigma by Β¬\neg, ∧\wedge, βˆƒx\exists x and the HΓ€rtig quantifier Hx(Ο†,ψ)\mathrm{H}x\,(\varphi, \psi), which binds xx in both formulas and is evaluated by π”„βŠ¨Hx(Ο†,ψ)⇔|{a∈A:π”„βŠ¨Ο†(a)}|=|{a∈A:π”„βŠ¨Οˆ(a)}|.\mathfrak A \models \mathrm{H}x\,(\varphi, \psi) \iff \bigl|\{a \in A : \mathfrak A \models \varphi(a)\}\bigr| = \bigl|\{a \in A : \mathfrak A \models \psi(a)\}\bigr|.(8)

For sets Οƒ\sigma and Οƒβ€²\sigma' of binary relation symbols, an interpretation ℐ\mathcal I of Οƒβ€²\sigma' in Οƒ\sigma consists of a domain formula Ξ±(x1,x2)\alpha(x_1, x_2), a formula Ξ΅(x1,x2,y1,y2)\varepsilon(x_1, x_2, y_1, y_2) identifying pairs, and a formula Ο†R(x1,x2,y1,y2)\varphi_R(x_1, x_2, y_1, y_2) for each RβˆˆΟƒβ€²R \in \sigma', all in the logic of (8) over Οƒ\sigma; it sends a finite Οƒ\sigma-structure 𝔄\mathfrak A to the Οƒβ€²\sigma'-structure ℐ(𝔄)\mathcal I(\mathfrak A) on the pairs that satisfy Ξ±\alpha, identified along Ξ΅\varepsilon, with the relations the Ο†R\varphi_R define.✦

An interpretation program PP over Οƒ\sigma consists of a finite vocabulary ΟƒP\sigma_P of state symbols, an initial interpretation ℐ0\mathcal I_0 of ΟƒP\sigma_P in Οƒ\sigma, a step interpretation ℐ1\mathcal I_1 of ΟƒP\sigma_P in ΟƒP\sigma_P, a halting sentence Ξ·\eta and an output sentence Ο‰\omega over ΟƒP\sigma_P.✦ The states of PP on a finite Οƒ\sigma-structure 𝔄\mathfrak A are 𝔄0=ℐ0(𝔄)\mathfrak A_0 = \mathcal I_0(\mathfrak A) and 𝔄j+1=ℐ1(𝔄j)\mathfrak A_{j+1} = \mathcal I_1(\mathfrak A_j).✦ The program PP halts at jj on 𝔄\mathfrak A when 𝔄j⊨η\mathfrak A_j \models \eta and 𝔄k⊭η\mathfrak A_k \not\models \eta for every k<jk < j, and accepts 𝔄\mathfrak A when it halts at some jj with 𝔄jβŠ¨Ο‰\mathfrak A_j \models \omega.✦ The cost of the run up to step jj is cost(𝔄,j)=(j+1)+βˆ‘k≀j|𝔄k|,\mathrm{cost}(\mathfrak A, j) = (j+1) + \sum_{k \le j} |\mathfrak A_k|,(9)✦ and PP is polynomially bounded when there are m,dβˆˆβ„•m, d \in \mathbb N such that on every finite Οƒ\sigma-structure 𝔄\mathfrak A with universe AA it halts at some jj with cost (9) at most m(|A|+1)dm\,(|A| + 1)^d.✦ An interpretation program decides a query when it is polynomially bounded and accepts exactly the structures that satisfy the query✦, and a query is definable by interpretations when some interpretation program decides it.✦

The Claim

Theorem 1. Let QQ be the separating query.

  1. For all inputs SS and TT over finite sets, Sβ‰…T⟹(Q(S)⇔Q(T)),Q∈PTIME,Qβˆ‰CPT.S \cong T \implies \bigl(Q(S) \iff Q(T)\bigr), \qquad Q \in \mathrm{PTIME}, \qquad Q \notin \mathrm{CPT}.(10)✦

  2. For every CPT program Ξ \Pi over Ο„\tau and all polynomials pp and qq with coefficients in β„•\mathbb N, there is an input SS over a finite set with Ξ  accepts S within (p,q)⇔¬Q(S).\Pi \text{ accepts } S \text{ within } (p,q) \iff \neg\, Q(S).(11)✦

  3. For every polynomially bounded interpretation program PP over Ο„\tau, there is a finite Ο„\tau-structure 𝔄\mathfrak A with P accepts 𝔄⇔¬Q(𝔄).P \text{ accepts } \mathfrak A \iff \neg\, Q(\mathfrak A).(12)✦

In the paper, the result reads: the query QQ on all finite structures in the fixed vocabulary Ο„\tau of eight binary relations is isomorphism-invariant and decidable in deterministic polynomial time, but is not definable in full choiceless polynomial time with counting.

What Is Checked

The library states (10), (11) and (12) over the separating query QQ, given by the system (2), (3) on inputs and on finite Ο„\tau-structures, over isomorphisms of inputs, over decision in polynomial time as in (4), over CPT programs accepting within polynomial bounds on their steps and on the objects (7) that occur, and over polynomially bounded interpretation programs in the logic of (8).