OctoInformBeta

OpenAI preprint, September 2026 · §7. Proof of the separation · §7

Proof of Theorem 1: fixing the parameters and comparing the runs: Every program or choiceless machine with polynomial bounds accepts both or neither of the grid structures Ab0A_{b^0} and Ab1A_{b^1} of some side LL

No choiceless machine with polynomial bounds decides the separating query.

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) computes on a finite structure by building hereditarily finite sets over its elements, without arbitrary choices, within polynomial bounds on its steps and on the sets it builds. Theorem 1 says that CPT does not capture polynomial time, and the query that separates the two is QQ: on a structure over a vocabulary τ\tau of eight binary relations, QQ asks whether a system of linear equations over 𝔽3=ℤ/3\mathbb F_3=\mathbb Z/3 read off the structure has a solution. The inputs compared are the grid structures Ab0A_{b^0} and Ab1A_{b^1} of two charges b0b^0 and b1b^1, which assign an element of 𝔽3\mathbb F_3 to each vertex of a cubic grid of side LL and differ at a single vertex.

Interpretation programs iterate a logical interpretation in first-order logic with the Härtig quantifier; choiceless machines, in the style of Blass, Gurevich and Shelah, run a rule on hereditarily finite sets.

The Query

The vocabulary τ\tau consists of the binary symbols Ed\mathrm{Ed}, Cf\mathrm{Cf}, EB\mathrm{EB}, VB\mathrm{VB}, II and ZδZ_\delta for δ∈𝔽3\delta\in\mathbb F_3.✦ An input structure 𝔄\mathfrak A on a finite set AA interprets each symbol of τ\tau as a binary relation on AA.✦ The edge atoms of 𝔄\mathfrak A form the set Y={y∈A:Ed(y,y)}Y=\{y\in A:\mathrm{Ed}(y,y)\}, its configuration atoms the set X={a∈A:Cf(a,a)}X=\{a\in A:\mathrm{Cf}(a,a)\}✦, and for a configuration atom t∈Xt\in X we put 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 there are a∈Xta\in X_t and x∈Yx\in Y with I(a,x)I(a,x) and EB(y,x)\mathrm{EB}(y,x).✦ The edge coefficient wa(y)∈𝔽3w_a(y)\in\mathbb F_3 of yy at a∈Xa\in X is the sum, over the edge atoms xx with I(a,x)I(a,x), of the scalars δ\delta with Zδ(y,x)Z_\delta(y,x).✦

Weights λ:X→𝔽3\lambda:X\to\mathbb F_3 are normalized, and weights μ:Y→𝔽3\mu:Y\to\mathbb F_3 are consistent with them, when ∑a∈Xtλ(a)=1(t∈X),μ(y)=∑a∈Xtλ(a)wa(y)(t∈X,y incident to t).\sum_{a\in X_t}\lambda(a)=1\quad(t\in X),\qquad \mu(y)=\sum_{a\in X_t}\lambda(a)\,w_a(y)\quad(t\in X,\ y\text{ incident to }t).(1) The query QQ holds of 𝔄\mathfrak A when there are normalized weights λ\lambda and weights μ\mu consistent with them.✦

The Grid Structures

The grid of side L=n+1≥2L=n+1\ge 2 has the vertex set V={0,…,L−1}3V=\{0,\dots,L-1\}^3.✦ The edges of the grid are the unit segments parallel to the axes: the edge ex(i,j,k)e_x(i,j,k) along xx has tail (i,j,k)(i,j,k) and head (i+1,j,k)(i+1,j,k), and the edges ey(i,j,k)e_y(i,j,k) and ez(i,j,k)e_z(i,j,k) along yy and zz run from (i,j,k)(i,j,k) to (i,j+1,k)(i,j+1,k) and to (i,j,k+1)(i,j,k+1); EE is the set of all of them. A vertex vv is incident to an edge ee when it is the head or the tail of ee✦, and the orientation sign ε(v,e)∈𝔽3\varepsilon(v,e)\in\mathbb F_3 is 11 if vv is the head of ee, −1-1 if it is the tail and 00 otherwise✦. The faces are the unit squares parallel to the xyxy, xzxz and yzyz planes, each given by its lowest corner, and FF is the set of them.✦ The face cycle γf∈𝔽3E\gamma_f\in\mathbb F_3^{E} of a face ff goes once around its boundary; for the face in the xyxy plane with lowest corner (i,j,k)(i,j,k) it is γf=𝟏ex(i,j,k)+𝟏ey(i+1,j,k)−𝟏ex(i,j+1,k)−𝟏ey(i,j,k),\gamma_f=\mathbf 1_{e_x(i,j,k)}+\mathbf 1_{e_y(i+1,j,k)} -\mathbf 1_{e_x(i,j+1,k)}-\mathbf 1_{e_y(i,j,k)},(2)✦ and the faces in the other two planes are traversed in the same way.

For a set Φ\Phi of faces, a group KK whose elements are called flows and a map γ:Φ→K\gamma:\Phi\to K, the support group H(γ)H(\gamma) is the central extension, attached to γ\gamma, of the group CΦC_\Phi of face labellings Φ→𝔽32\Phi\to\mathbb F_3^2 by KK; its elements are the pairs of a face labelling and a flow.✦ The faces on an edge ee form the set Fe={f∈F:γf(e)≠0}F_e=\{f\in F:\gamma_f(e)\neq 0\} of squares with ee as a side✦, and the local cycle of ee sends f∈Fef\in F_e to γf(e)\gamma_f(e)✦. The local group HeH_e of ee is the support group of its local cycle, with flows in 𝔽3\mathbb F_3.✦

A local state ss at a vertex vv assigns to each edge ee at vv an element s(e)s(e) of HeH_e✦; it is compatible when, for any two edges ee and e′e' at vv and any face ff on both, s(e)s(e) and s(e′)s(e') have the same component at ff.✦ The divergence of a local state ss at vv is the net flow into vv, where the flow of an element of HeH_e is its second component, divs=∑e at vε(v,e)flow(s(e)).\mathrm{div}\,s=\sum_{e\text{ at }v}\varepsilon(v,e)\,\mathrm{flow}(s(e)).(3) For a charge b∈𝔽3Vb\in\mathbb F_3^V, a configuration at vv is a compatible local state at vv of divergence b(v)b(v).✦

The atoms of bb are of two disjoint sorts: the edge atoms (e,g)(e,g) with g∈Heg\in H_e, and the configuration atoms (v,s)(v,s) with ss a configuration at vv.✦ The grid structure AbA_b is the structure over τ\tau whose universe is the set of atoms of bb and whose relations hold exactly as follows: Ed\mathrm{Ed} relates each edge atom to itself and Cf\mathrm{Cf} each configuration atom to itself; EB\mathrm{EB} relates any two edge atoms over the same edge, and VB\mathrm{VB} any two configuration atoms over the same vertex; II relates (v,s)(v,s) to (e,s(e))(e,s(e)) for every edge ee at vv; and ZδZ_\delta relates (e,g)(e,g) to (e,h)(e,h) when g−1hg^{-1}h has flow δ\delta. The two charges, defined for a vertex v*v^* of the grid, are b0=0b^0=0 and b1=𝟏v*b^1=\mathbf 1_{v^*}, equal to 11 at v*v^* and to 00 elsewhere.✦

Interpretation Programs

A finite structure 𝔄\mathfrak A over a set RR of binary relation symbols is a finite universe V(𝔄)V(\mathfrak A) with a binary relation r𝔄r^{\mathfrak A} on it for each r∈Rr\in R.✦ The formulas of first-order logic with the Härtig quantifier, FO+𝖧\mathrm{FO}+\mathsf H, over RR in nn variables are built from ⊥\bot, xi=xjx_i=x_j and r(xi,xj)r(x_i,x_j) by negation, conjunction, ∃yφ\exists y\,\varphi and 𝖧y(φ,ψ)\mathsf Hy\,(\varphi,\psi), the two quantifiers binding a new variable yy.✦ Satisfaction is defined by recursion, with 𝖧y(φ,ψ)\mathsf Hy\,(\varphi,\psi) true when as many elements satisfy φ\varphi as satisfy ψ\psi, and a sentence ψ\psi holds in 𝔄\mathfrak A, written 𝔄⊨ψ\mathfrak A\models\psi, when the empty assignment satisfies it.✦ The scoped width of a formula is the largest number of variables in scope at any of its atomic subformulas.✦

A two-dimensional interpretation ℐ\mathcal I of structures over R′R' in structures over RR consists of FO+𝖧\mathrm{FO}+\mathsf H formulas over RR: a domain formula in two variables, an equivalence formula in four, and for each symbol of R′R' a relation formula in four.✦ The interpretation ℐ\mathcal I sends a finite structure 𝔄\mathfrak A over RR to the structure ℐ(𝔄)\mathcal I(\mathfrak A) over R′R' whose elements are the pairs of elements of 𝔄\mathfrak A satisfying the domain formula, identified when they satisfy the equivalence formula, and whose relations are given by the relation formulas. An interpretation program PP over RR consists of a finite vocabulary RPR_P of state symbols, an initial interpretation ℐinit\mathcal I_{\mathrm{init}} of structures over RPR_P in structures over RR, a step interpretation ℐstep\mathcal I_{\mathrm{step}} of structures over RPR_P in structures over RPR_P, and two sentences over RPR_P, the halting condition ψhalt\psi_{\mathrm{halt}} and the output condition ψout\psi_{\mathrm{out}}.✦ The states of PP on a finite structure 𝔄\mathfrak A over RR are 𝔄0=ℐinit(𝔄)\mathfrak A_0=\mathcal I_{\mathrm{init}}(\mathfrak A) and 𝔄j+1=ℐstep(𝔄j)\mathfrak A_{j+1}=\mathcal I_{\mathrm{step}}(\mathfrak A_j).✦

A step hh is the first halting step of PP on 𝔄\mathfrak A when 𝔄h⊨ψhalt\mathfrak A_h\models\psi_{\mathrm{halt}} and 𝔄k⊭ψhalt\mathfrak A_k\not\models\psi_{\mathrm{halt}} for every k<hk<h✦, and PP accepts 𝔄\mathfrak A when it has a first halting step hh with 𝔄h⊨ψout\mathfrak A_h\models\psi_{\mathrm{out}}.✦ The cost of PP on 𝔄\mathfrak A up to step jj counts the states and their elements, costP(𝔄,j)=(j+1)+∑k=0j|V(𝔄k)|,\mathrm{cost}_P(\mathfrak A,j)=(j+1)+\sum_{k=0}^{j}|V(\mathfrak A_k)|,(4)✦ and PP is polynomially bounded when there are natural numbers aa and dd such that on every finite structure 𝔄\mathfrak A over RR it has a first halting step hh with costP(𝔄,h)≤a(|V(𝔄)|+1)d\mathrm{cost}_P(\mathfrak A,h)\le a\,(|V(\mathfrak A)|+1)^d.✦

Choiceless Machines

The hereditarily finite objects HF(A)\mathrm{HF}(A) over a set AA of atoms are the atoms, which have no elements, and the finite sets of such objects, two sets being equal when they have the same elements.✦ The rank of an object is 00 for an atom and for the empty set, and otherwise one more than the largest rank of its elements.✦ The transitive closure of an object xx is tc(x)={x}∪⋃y∈xtc(y)\mathrm{tc}(x)=\{x\}\cup\bigcup_{y\in x}\mathrm{tc}(y)✦, and the closure of a finite family of objects is the union of the transitive closures of its members.✦ The von Neumann ordinals are [0]=∅[0]=\emptyset and [i+1]=[i]∪{[i]}[i+1]=[i]\cup\{[i]\}✦; the empty set 0=[0]0=[0] stands for false✦ and 1=[1]={0}1=[1]=\{0\} for true✦, and Atoms\mathrm{Atoms} is the set of all atoms of AA.✦

A choiceless machine PP over a vocabulary RR consists of a finite set of dynamic function symbols, each with an arity, and a rule (defined below) without free variables, written in these symbols, the input relations of RR and two nullary control flags, halt\mathrm{halt} and accept\mathrm{accept}.✦ A machine state σ\sigma assigns an object of HF(A)\mathrm{HF}(A) to every dynamic function symbol applied to a tuple of objects of the length of its arity, all but finitely many of these values being the empty set; terms in kk free variables, and their values in σ\sigma under an assignment of objects to the variables, are given by recursion.✦ A variable takes its assigned value, the constant [n][n] the ordinal [n][n], Atoms\mathrm{Atoms} the set of all atoms, and f(t1,…,tr)f(t_1,\dots,t_r) the value of σ\sigma at ff and the values of t1,…,trt_1,\dots,t_r. The pair {s,t}\{s,t\}, the union ⋃t\bigcup t, the unique element of tt and the cardinality of tt are formed from the values. The tests s=ts=t, s∈ts\in t, “tt is an atom” and r(s,t)r(s,t) for r∈Rr\in R, the negation ¬t\neg t and the conjunction s∧ts\wedge t take the value 11 when they hold and 00 otherwise, a term counting as true when its value is 11. The conditional iftthent1elset2\mathrm{if}\ t\ \mathrm{then}\ t_1\ \mathrm{else}\ t_2 takes the value of t1t_1 when tt is true and that of t2t_2 otherwise, and the comprehension {u(x):x∈t,g(x)}\{u(x):x\in t,\ g(x)\} of two terms uu and gg, in which xx is bound, is the set of the values of u(x)u(x) for the elements xx of tt at which g(x)g(x) is true.

The rules over these terms are skip\mathrm{skip}, the update f(t1,…,tr):=tf(t_1,\dots,t_r):=t, the parallel composition of two rules, the conditional rule iftthenΠ1elseΠ2\mathrm{if}\ t\ \mathrm{then}\ \Pi_1\ \mathrm{else}\ \Pi_2, and the rules forallx∈tdoΠ\mathrm{forall}\ x\in t\ \mathrm{do}\ \Pi and letx=tinΠ\mathrm{let}\ x=t\ \mathrm{in}\ \Pi, which bind xx.✦

A location is a function symbol ff together with a tuple of objects whose length is the arity of ff.✦ The states of PP are the machine states on the locations of its function symbols and its flags.✦ The support of σ\sigma is the finite set of locations with a nonempty value✦, and its critical sets are the values and the arguments at these locations✦. The active sets Act(σ)\mathrm{Act}(\sigma) form the closure of the family made of the critical sets, Atoms\mathrm{Atoms}, 00, 11 and the atoms of AA.✦ A flag holds in σ\sigma when its value there is 11.✦ One step of the rule in a state σ\sigma evaluates the rule in σ\sigma, which yields updates of locations, and applies these updates to σ\sigma. On an input structure on AA, the run of PP is the sequence of states σ0,σ1,…\sigma_0,\sigma_1,\dots that starts from the initial state, in which every location holds the empty set, and passes to the next state by one step of the rule, for as long as that step is defined.✦

An observer OO of PP is a term without free variables in the symbols of PP, with value O(σ)O(\sigma) in a state σ\sigma.✦ The observed sets up to step hh are ObsO(h)=⋃j≤hAct(σj)∪⋃j<h⋃y∈O(σj)tc(y),\mathrm{Obs}_O(h)=\bigcup_{j\le h}\mathrm{Act}(\sigma_j)\ \cup\ \bigcup_{j<h}\,\bigcup_{y\in O(\sigma_j)}\mathrm{tc}(y),(5)✦ the unions running over the steps the run reaches. For polynomials TT and SS with natural coefficients and an input structure 𝔄\mathfrak A on a finite set AA, PP accepts 𝔄\mathfrak A with observer OO in time TT and space SS, written AccOT,S(P,𝔄)\mathrm{Acc}^{T,S}_O(P,\mathfrak A), when the run on 𝔄\mathfrak A reaches, at some step h≤T(|A|)h\le T(|A|), a state in which both halt\mathrm{halt} and accept\mathrm{accept} hold, and |ObsO(h)|≤S(|A|)|\mathrm{Obs}_O(h)|\le S(|A|).✦

Numeric Bounds

For natural numbers aa and dd, the time exponent is e=a+2d+2e=a+2d+2✦ and the trace exponent is q=3e+4q=3e+4✦. The palette size of a real number LL is M(L)=⌊L7/4⌋M(L)=\lfloor L^{7/4}\rfloor✦, and for reals CC and qq the radius is ρC,q(L)=⌈2L(qlog⁡3(CL3))2⌉\rho_{C,q}(L)=\lceil 2L\,(q\log_3(CL^3))^2\rceil✦. For a grid side LL, a number NN of atoms and a trace exponent qq, the box radius is ρ=⌈2L(qlog⁡3N)2⌉\rho=\lceil 2L\,(q\log_3 N)^2\rceil, the radius ρC,q(L)\rho_{C,q}(L) with N=CL3N=CL^3. The box constant is c=1−2−1/3c=1-2^{-1/3}.✦ A grid side L=n+1L=n+1 and a number MM of variables satisfy the giant component bound when (12M/c)3/2<L3(12M/c)^{3/2}<L^3.✦ The local size bound is 3253^{25}✦, and the atom size constant is 3⋅325+31503\cdot 3^{25}+3^{150}✦.

The Claim

Theorem 1. (a) Let aa and dd be natural numbers with time exponent ee and trace exponent qq, and let N≥2N\ge 2 be a natural number. Then 2≤Ne,N≤Ne,a(N+1)d≤Ne,9(Ne)3≤Nq.2\le N^{e},\qquad N\le N^{e},\qquad a\,(N+1)^{d}\le N^{e},\qquad 9\,(N^{e})^{3}\le N^{q}.(6)✦

(b) Let C>0C>0, qq and κ>0\kappa>0 be reals and mm a natural number. For every sufficiently large real LL, the radius ρ=ρC,q(L)\rho=\rho_{C,q}(L) and the palette size M=M(L)M=M(L) satisfy max⁡(4,m+1)ρ≤M,7max⁡(2,m)ρ+7(6max⁡(2,m)ρκ)3/2+1≤M,(12Mκ)3/2<L3.\max(4,m+1)\,\rho\le M,\qquad 7\max(2,m)\,\rho+7\Bigl(\frac{6\max(2,m)\,\rho}{\kappa}\Bigr)^{3/2}+1\le M,\qquad \Bigl(\frac{12M}{\kappa}\Bigr)^{3/2}<L^3.(7)✦

(c) Let q≥1q\ge 1 and mm be natural numbers. There is a grid side L=n+1≥2L=n+1\ge 2 such that, with NN the bound on its number of atoms, M=⌊L7/4⌋M=\lfloor L^{7/4}\rfloor its palette size and ρ\rho the box radius, the numbers LL and MM satisfy the giant component bound and ρ>0,max⁡(4,m+1)ρ≤M,7max⁡(2,m)ρ+7(6max⁡(2,m)ρc)3/2+1≤M.\rho>0,\qquad \max(4,m+1)\,\rho\le M,\qquad 7\max(2,m)\,\rho+7\Bigl(\frac{6\max(2,m)\,\rho}{c}\Bigr)^{3/2}+1\le M.(8)✦

(d) Let PP be an interpretation program over τ\tau, let L=n+1L=n+1 be a grid side with a vertex v*v^*, and let LL, NN, MM, qq and mm satisfy the giant component bound and the conditions (8). Then for every step jj less than a step bound JJ, a natural number fixed by the data of the hypotheses, and every sentence ψ\psi of FO+𝖧\mathrm{FO}+\mathsf H over the state symbols of PP of scoped width less than mm, (Ab0)j⊨ψ⇔(Ab1)j⊨ψ.(A_{b^0})_j\models\psi\iff(A_{b^1})_j\models\psi.(9)✦

(e) Let PP be an interpretation program over RR with first halting steps jj on a finite structure 𝔄\mathfrak A and kk on a finite structure 𝔅\mathfrak B, and suppose that at every step l≤min⁡(j,k)l\le\min(j,k) the states 𝔄l\mathfrak A_l and 𝔅l\mathfrak B_l agree on ψhalt\psi_{\mathrm{halt}} and on ψout\psi_{\mathrm{out}}. Then j=kand(P accepts 𝔄⇔P accepts 𝔅).j=k\quad\text{and}\quad\bigl(P\text{ accepts }\mathfrak A\iff P\text{ accepts }\mathfrak B\bigr).(10)✦

(f) Let PP be a polynomially bounded interpretation program over τ\tau. There are a grid side L=n+1≥2L=n+1\ge 2 and a vertex v*v^* with P accepts Ab0⇔P accepts Ab1.P\text{ accepts }A_{b^0}\iff P\text{ accepts }A_{b^1}.(11)✦

(g) Let PP be a choiceless machine over τ\tau with an observer OO, and let TT and SS be polynomials with natural coefficients. There are a grid side L=n+1≥2L=n+1\ge 2 and a vertex v*v^* with AccOT,S(P,Ab0)⇔AccOT,S(P,Ab1).\mathrm{Acc}^{T,S}_O(P,A_{b^0})\iff\mathrm{Acc}^{T,S}_O(P,A_{b^1}).(12)✦

(h) Under the hypotheses of (g), there is an input structure 𝔄\mathfrak A on a finite set with AccOT,S(P,𝔄)⇔Q fails in 𝔄.\mathrm{Acc}^{T,S}_O(P,\mathfrak A)\iff Q\text{ fails in }\mathfrak A.(13)✦

What Is Checked

The claims are stated over the grid structures Ab0A_{b^0} and Ab1A_{b^1} with their atoms, local groups and configurations, over the query QQ, over interpretation programs in FO+𝖧\mathrm{FO}+\mathsf H with their states, first halting steps, acceptance and cost, over choiceless machines on HF(A)\mathrm{HF}(A) with an observer and their observed sets, and over the time and trace exponents, the radius, the palette size and the giant component bound.