OctoInformBeta

OpenAI preprint, September 2026 · §1. Introduction

Proposition 2: The separating query QQ is invariant under isomorphism, and a multi-tape Turing machine running Gaussian elimination decides it on ordered encodings in polynomial time

The separating query is a polynomial-time 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) does not capture polynomial time: there is a query QQ on finite structures that a polynomial-time algorithm decides and no CPT program defines. Proposition 2 is the upper bound.

A structure for QQ describes a system of linear equations over the field 𝔽3\mathbb{F}_3 of integers modulo 33, with unknowns attached to elements of the structure, and QQ asks whether the system has a solution. Gaussian elimination decides it.

The Query

The vocabulary τ\tau consists of eight binary relation symbols: Ed\mathrm{Ed}, Cf\mathrm{Cf}, EB\mathrm{EB}, VB\mathrm{VB}, II, and ZδZ_\delta for each δ∈𝔽3\delta\in\mathbb{F}_3.✦ An input structure SS on a set AA is a τ\tau-structure with universe AA: it interprets each R∈τR\in\tau as a binary relation RSR^S on AA.✦ An isomorphism from an input structure SS on AA to an input structure TT on BB is a bijection f:A→Bf\colon A\to B such that RT(f(x),f(y))R^T(f(x),f(y)) holds exactly when RS(x,y)R^S(x,y) does, for every R∈τR\in\tau and all x,y∈Ax,y\in A.✦

The edge atoms of an input structure SS on a finite set AA 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 t∈Xt\in X we write Xt={a∈X:VB(t,a)}X_t=\{a\in X:\mathrm{VB}(t,a)\}, the relations being those of SS. The coefficient of an edge atom yy in a configuration atom aa is the element of 𝔽3\mathbb{F}_3 ca(y)=∑x∈Y,I(a,x)∑δ∈𝔽3,Zδ(y,x)δ.c_a(y)=\sum_{x\in Y,\ I(a,x)}\ \sum_{\delta\in\mathbb{F}_3,\ Z_\delta(y,x)}\delta .(1)✦ A configuration atom tt is incident to an edge atom yy if 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).✦

A weighting of SS is a pair of maps λ:X→𝔽3\lambda\colon X\to\mathbb{F}_3 and μ:Y→𝔽3\mu\colon Y\to\mathbb{F}_3. The map λ\lambda is normalized if ∑a∈Xtλ(a)=1for every t∈X,\sum_{a\in X_t}\lambda(a)=1\quad\text{for every } t\in X,(2)✦ and a weighting (λ,μ)(\lambda,\mu) of SS is consistent if μ(y)=∑a∈Xtλ(a)ca(y)for every t∈X and every y∈Y incident to t.\mu(y)=\sum_{a\in X_t}\lambda(a)\,c_a(y)\quad\text{for every } t\in X \text{ and every } y\in Y \text{ incident to } t.(3) The query QQ holds of SS if SS has a consistent weighting (λ,μ)(\lambda,\mu) with λ\lambda normalized.

Linear Systems and Elimination

A linear equation over 𝔽3\mathbb{F}_3 in nn unknowns consists of coefficients r∈𝔽3nr\in\mathbb{F}_3^n and a right-hand side b∈𝔽3b\in\mathbb{F}_3✦, and a vector v∈𝔽3nv\in\mathbb{F}_3^n satisfies it if ∑i<nrivi=b\sum_{i<n}r_iv_i=b.✦ A linear system EE in nn unknowns is a finite sequence of such equations, and it is solvable if one vector satisfies all of them.✦

Gaussian elimination computes a verdict gauss(E)∈{0,1}\mathrm{gauss}(E)\in\{0,1\} one unknown at a time. With no unknowns left, the verdict is 11 if every right-hand side is 00, and 00 otherwise. With n+1n+1 unknowns, if some equation has a nonzero coefficient at the first unknown, it serves as pivot, and a multiple of it is subtracted from each equation to make that coefficient 00; pivot or not, the first unknown is then dropped. Counted elimination performs the same elimination and also returns an operation count ops(E)\mathrm{ops}(E): for a system of mm equations it charges (8n+12)m+2(8n+12)m+2 for each unknown dropped while n+1n+1 remain, and 2m+12m+1 for the final check.✦

An ordered input of size NN is an input structure SS on {0,…,N−1}\{0,\dots,N-1\}.✦ The linear system ESE_S of an ordered input SS of size NN has the 2N2N unknowns λ0,…,λN−1,μ0,…,μN−1\lambda_0,\dots,\lambda_{N-1},\mu_0,\dots,\mu_{N-1} and N+N2N+N^2 equations. First comes, for each tt, the equation ∑a∈Xtλa=1\sum_{a\in X_t}\lambda_a=1 of (2) when t∈Xt\in X; then, for each pair (t,y)(t,y) in lexicographic order, the equation μy−∑a∈Xtca(y)λa=0\mu_y-\sum_{a\in X_t}c_a(y)\,\lambda_a=0 of (3) when t∈Xt\in X, y∈Yy\in Y and tt is incident to yy; every other equation is 0=00=0.✦ The decision dec(S)\mathrm{dec}(S) is the verdict of counted elimination on ESE_S.✦ The answer ans(N,S)\mathrm{ans}(N,S) is the verdict of Gaussian elimination on ESE_S with each equation written as the list of its 2N2N coefficients and its right-hand side.✦

The Machine

The ordered encoding of an ordered input SS of size NN is the word ⟨S⟩=▫N0β(S)\langle S\rangle=\square^N\,0\,\beta(S)(4)✦ over the alphabet consisting of the blank symbol ▫\square and the digits 0,1,20,1,2, where the table β(S)∈{0,1}8N2\beta(S)\in\{0,1\}^{8N^2} lists the truth values of R(a,b)R(a,b), with 11 for true, for RR in the order Ed\mathrm{Ed}, Cf\mathrm{Cf}, EB\mathrm{EB}, VB\mathrm{VB}, II, Z0Z_0, Z1Z_1, Z2Z_2 and (a,b)(a,b) in lexicographic order.

The machine that decides QQ on ordered encodings is a multi-tape Turing machine in which each tape is a stack, built from programs in three languages: stack programs, counter programs and bounded programs. A stack program acts on finitely many stacks and a control value from a finite set. Its atomic actions push a letter computed from the control, read or pop the top letter of a stack into the control, update the control, and branch on it✦; programs are built from them by sequencing, conditionals and while loops on a test of the control.✦ A run between two stores, each a control value with the contents of every stack, takes one step for an atomic action and for leaving a loop, and one step more than its parts for a sequence, a conditional or a pass through a loop.✦ Some stack programs are fixed once and for all: they move, copy and clear stacks, and combine the contents of two stacks, each read as a row of letters, letter by letter. Each stack program compiles into a multi-tape Turing machine whose tapes are its stacks, one of them for input and one for output, and whose states are the nodes of the program, namely its atomic actions and the programs built from them; the start and the exit of the program are the nodes at which a run of it begins and ends.✦

A counter program has finitely many registers holding natural numbers, a finite control, an input word and an output word. Its atomic actions update the control, set a register to zero, increment or decrement it, test whether it is positive, copy or add one register into another, look up an input letter by a register, consume the next input letter and emit an output letter; they combine as in stack programs.✦ A counter program compiles into a stack program that keeps each register in unary on a stack of its own, beside stacks for the input and the output and three scratch stacks.✦

The letters of the counter programs, of the elimination program and of the query program are the scalars 0,1,20,1,2 of 𝔽3\mathbb{F}_3 together with a blank ▫\square, which also separates rows.

A bounded program has five index variables t,y,a,x,zt,y,a,x,z and a finite control. It is built by sequencing from updates of the control, emissions of a letter, reads of the table bit R(i,j)R(i,j) for R∈τR\in\tau and index variables i,ji,j, tests of i=ji=j, and loops in which an index variable runs through 0,…,N−10,\dots,N-1.✦ The time bound θN(P)\theta_N(P) of a bounded program PP, with ℓ=8N2\ell=8N^2, charges 11 for an update, 33 for an emission, 1000(N+1)2+10ℓ1000(N+1)^2+10\ell for a read, 100(N+1)100(N+1) for a test, one more than the sum of the parts for a sequence, and (θN(B)+13)N+22(\theta_N(B)+13)N+22 for a loop with body BB.✦ A bounded program compiles into a counter program with registers for NN, for 2N2N, for each index variable and its remaining count, and for scratch values.✦

The matrix program PmatP_{\mathrm{mat}} is the bounded program that emits ESE_S, each equation as its 2N2N coefficients, its right-hand side and a blank ▫\square, with incidence and each coefficient ca(y)c_a(y) computed by loops over the universe.✦ The elimination program is a stack program that keeps the equations on a matrix stack and performs the Gaussian elimination described above on the 2N2N columns, writing the verdict to its output.✦

The query program reads NN off the leading blanks of its input, runs the compiled matrix program, moves the emitted equations and 2N2N in unary onto the stacks of the elimination program, runs it, and clears what remains of the input.✦ The query machine MQM_Q is the Turing machine compiled from the query program✦, and its step bound is T(N)=θN(Pmat)+2(N+N2)(2N+2)+300(N+N2+1)(2N+3)2+14N+16N2+23.T(N)=\theta_N(P_{\mathrm{mat}})+2(N+N^2)(2N+2)+300(N+N^2+1)(2N+3)^2+14N+16N^2+23.(5)✦

The Claim

Theorem 1. Let SS and TT be input structures on finite sets, and suppose there is an isomorphism from SS to TT. Then Q(S)⇔Q(T).Q(S)\iff Q(T).(6)✦ For every linear system EE over 𝔽3\mathbb{F}_3, gauss(E)=1⇔E is solvable.\mathrm{gauss}(E)=1\iff E\text{ is solvable}.(7)✦ For every ordered input SS of size NN, ES is solvable⇔Q(S),E_S\text{ is solvable}\iff Q(S),(8)✦ ops(ES)≤96(N+1)4,\mathrm{ops}(E_S)\le 96\,(N+1)^4,(9)✦ dec(S)=1⇔Q(S),\mathrm{dec}(S)=1\iff Q(S),(10)✦ ans(N,S)=1⇔Q(S).\mathrm{ans}(N,S)=1\iff Q(S).(11)✦ There is a polynomial pp with natural-number coefficients such that, for every N∈ℕN\in\mathbb{N}, T(N)=p(N).T(N)=p(N).(12)✦ There are a multi-tape Turing machine MM and a polynomial qq such that, for every ordered input SS of size NN, the machine MM started with ⟨S⟩\langle S\rangle on its input tape halts within q(|⟨S⟩|)q(|\langle S\rangle|) steps with a one-letter output M(⟨S⟩)M(\langle S\rangle), and M(⟨S⟩)=ans(N,S).M(\langle S\rangle)=\mathrm{ans}(N,S).(13)✦

What Is Checked

The claim is stated over input structures, their isomorphisms and the query QQ in (6); over linear systems over 𝔽3\mathbb{F}_3 and Gaussian elimination in (7); over ordered inputs, their systems ESE_S, counted elimination and the answer ans\mathrm{ans} in (8), (9), (10) and (11); over the step bound TT of the query machine in (12); and over multi-tape Turing machines and the ordered encoding (4) in (13).

About the programs, the library proves that a run of a stack program from one store to another in nn steps is followed by every Turing machine containing the program’s compiled code, which passes within nn steps from the first store at the program’s start to the second at its exit✦, and for the compiled machine itself the exit is halting. It also proves that the query program, started with ⟨S⟩\langle S\rangle on its input stack and every other stack empty, runs in at most T(N)T(N) steps to the store in which every stack is empty except the output stack, which holds the one letter ans(N,S)\mathrm{ans}(N,S).✦