OctoInformBeta

OpenAI preprint, September 2026 · §6. Encoding complete choiceless computations · §6

Interpretation programs: Two-dimensional interpretations taken modulo a generated equivalence, and programs that decide a query with cost polynomial in the input size

Programs that iterate logical interpretations with the Härtig quantifier.

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 computes on a finite structure without ever choosing an element, so all it can build is what is definable from the input as a whole. Interpretation programs give such a computation a form with no machine in it: a run is a sequence of finite structures, each defined from the one before by a logical interpretation in first-order logic with the Härtig quantifier.

Structures and Formulas

Fix a set RR of binary relation symbols. A finite structure 𝔄\mathfrak A over RR is a finite set V(𝔄)V(\mathfrak A), its universe, together with a binary relation r𝔄r^{\mathfrak A} on V(𝔄)V(\mathfrak A) for each r∈Rr\in R: 𝔄=(V(𝔄),(r𝔄)r∈R),r𝔄⊆V(𝔄)×V(𝔄).\mathfrak A=\bigl(V(\mathfrak A),\,(r^{\mathfrak A})_{r\in R}\bigr),\qquad r^{\mathfrak A}\subseteq V(\mathfrak A)\times V(\mathfrak A).(1)✦

The formulas of first-order logic with the Härtig quantifier, FO+𝖧\mathrm{FO}+\mathsf H, over RR in the variables x1,…,xnx_1,\dots,x_n are generated by φ,ψ::=⊥∣xi=xj∣r(xi,xj)∣¬φ∣φ∧ψ∣∃yφ∣𝖧y(φ,ψ),\varphi,\psi\;::=\;\bot\;\mid\;x_i=x_j\;\mid\;r(x_i,x_j)\;\mid\;\neg\varphi\;\mid\; \varphi\wedge\psi\;\mid\;\exists y\,\varphi\;\mid\;\mathsf Hy\,(\varphi,\psi),(2)✦ with r∈Rr\in R and 1≤i,j≤n1\le i,j\le n; in the last two clauses φ\varphi and ψ\psi are formulas in the n+1n+1 variables y,x1,…,xny,x_1,\dots,x_n, and yy is bound.

Satisfaction 𝔄⊨φ[a‾]\mathfrak A\models\varphi[\bar a] of a formula in nn variables under an assignment a‾∈V(𝔄)n\bar a\in V(\mathfrak A)^n is the usual one for ⊥\bot, equality, atoms, ¬\neg, ∧\wedge and ∃\exists, and for the Härtig quantifier it is 𝔄⊨𝖧y(φ,ψ)[a‾]⇔|{b∈V(𝔄):𝔄⊨φ[b,a‾]}|=|{b∈V(𝔄):𝔄⊨ψ[b,a‾]}|,\mathfrak A\models\mathsf Hy\,(\varphi,\psi)[\bar a]\iff \bigl|\{b\in V(\mathfrak A):\mathfrak A\models\varphi[b,\bar a]\}\bigr| =\bigl|\{b\in V(\mathfrak A):\mathfrak A\models\psi[b,\bar a]\}\bigr|,(3)✦ with bb assigned to yy. A sentence ψ\psi over RR is a formula of FO+𝖧\mathrm{FO}+\mathsf H over RR in no variables; it holds in 𝔄\mathfrak A, written 𝔄⊨ψ\mathfrak A\models\psi, when it is satisfied under the empty assignment.✦

Interpretations

Let RR and TT be sets of binary relation symbols. A two-dimensional interpretation ℐ\mathcal I of structures over TT in structures over RR is a family of formulas of FO+𝖧\mathrm{FO}+\mathsf H over RR, ℐ=(δ(x1,x2),η(x‾,y‾),(ρt(x‾,y‾))t∈T),x‾=(x1,x2),y‾=(y1,y2),\mathcal I=\bigl(\delta(x_1,x_2),\ \eta(\bar x,\bar y),\ (\rho_t(\bar x,\bar y))_{t\in T}\bigr), \qquad \bar x=(x_1,x_2),\ \bar y=(y_1,y_2),(4)✦ made of a domain formula δ\delta in two variables, an equivalence formula η\eta in four, and a relation formula ρt\rho_t in four for each symbol t∈Tt\in T.

Let 𝔄\mathfrak A be a finite structure over RR. The domain of ℐ\mathcal I on 𝔄\mathfrak A is the set of pairs D={(a1,a2)∈V(𝔄)2:𝔄⊨δ[a1,a2]}.D=\{(a_1,a_2)\in V(\mathfrak A)^2:\mathfrak A\models\delta[a_1,a_2]\}.(5)✦ Two pairs a‾,b‾∈D\bar a,\bar b\in D are linked when 𝔄⊨η[a‾,b‾]\mathfrak A\models\eta[\bar a,\bar b]✦, and ≈{\approx} is the equivalence relation on DD generated by the links, the smallest one containing them.✦ The interpreted structure ℐ(𝔄)\mathcal I(\mathfrak A) is the finite structure over TT whose universe is the set V(ℐ(𝔄))=D/≈V(\mathcal I(\mathfrak A))=D/{\approx} of classes [a‾][\bar a], and in which tt holds between two classes when some representatives of them satisfy ρt\rho_t: ℐ(𝔄)=(D/≈,(tℐ(𝔄))t∈T),([a‾],[b‾])∈tℐ(𝔄)⇔𝔄⊨ρt[a‾′,b‾′] for some a‾′≈a‾,b‾′≈b‾.\begin{aligned} \mathcal I(\mathfrak A)&=\bigl(D/{\approx},\,(t^{\mathcal I(\mathfrak A)})_{t\in T}\bigr),\\ ([\bar a],[\bar b])\in t^{\mathcal I(\mathfrak A)}&\iff \mathfrak A\models\rho_t[\bar a',\bar b']\text{ for some }\bar a'\approx\bar a,\ \bar b'\approx\bar b. \end{aligned}(6)✦

The Definition

Definition 1. Let RR be a set of binary relation symbols. An interpretation program PP over RR is a tuple P=(S,ℐinit,ℐstep,ψhalt,ψout),P=(S,\ \mathcal I_{\mathrm{init}},\ \mathcal I_{\mathrm{step}},\ \psi_{\mathrm{halt}},\ \psi_{\mathrm{out}}),(7)✦ where SS is a finite set of binary relation symbols, the state symbols, ℐinit\mathcal I_{\mathrm{init}} is an interpretation of structures over SS in structures over RR, ℐstep\mathcal I_{\mathrm{step}} is an interpretation of structures over SS in structures over SS, and the halting condition ψhalt\psi_{\mathrm{halt}} and the output condition ψout\psi_{\mathrm{out}} are sentences of FO+𝖧\mathrm{FO}+\mathsf H over SS.

Let 𝔄\mathfrak A be a finite structure over RR. The state 𝔄j\mathfrak A_j of PP after jj steps on 𝔄\mathfrak A is the finite structure over SS given by 𝔄0=ℐinit(𝔄),𝔄j+1=ℐstep(𝔄j).\mathfrak A_0=\mathcal I_{\mathrm{init}}(\mathfrak A),\qquad \mathfrak A_{j+1}=\mathcal I_{\mathrm{step}}(\mathfrak A_j).(8)✦ A natural number hh is the first halting step of PP on 𝔄\mathfrak A when 𝔄h⊨ψhaltand𝔄k⊭ψhaltfor every k<h.\mathfrak A_h\models\psi_{\mathrm{halt}}\quad\text{and}\quad \mathfrak A_k\not\models\psi_{\mathrm{halt}}\ \text{for every }k<h.(9)✦ The cost of PP on 𝔄\mathfrak A up to step jj is the number j+1j+1 of the states 𝔄0,…,𝔄j\mathfrak A_0,\dots,\mathfrak A_j plus the sum of their sizes, costP(𝔄,j)=(j+1)+∑k=0j|V(𝔄k)|.\mathrm{cost}_P(\mathfrak A,j)=(j+1)+\sum_{k=0}^{j}|V(\mathfrak A_k)|.(10)✦ The program PP accepts 𝔄\mathfrak A when it has a first halting step hh on 𝔄\mathfrak A and 𝔄h⊨ψout.\mathfrak A_h\models\psi_{\mathrm{out}}.(11)✦ The program PP over RR is polynomially bounded when there are natural numbers cc and dd such that on every finite structure 𝔄\mathfrak A over RR the program PP has a first halting step hh with costP(𝔄,h)≤c(|V(𝔄)|+1)d.\mathrm{cost}_P(\mathfrak A,h)\le c\,\bigl(|V(\mathfrak A)|+1\bigr)^d.(12)✦ For a query QQ, a property of finite structures over RR, the program PP decides QQ when it is polynomially bounded and, for every finite structure 𝔄\mathfrak A over RR, P accepts 𝔄⇔Q(𝔄).P\text{ accepts }\mathfrak A\iff Q(\mathfrak A).(13)✦

In the paper, the result reads: an interpretation is given by formulas δ(x1,x2)\delta(x_1,x_2), η(x‾,y‾)\eta(\bar x,\bar y) and ρt(x‾,y‾)\rho_t(\bar x,\bar y) of first-order logic with the Härtig quantifier, its universe is the domain modulo the equivalence generated by η\eta, and tt holds on classes when some representatives satisfy ρt\rho_t, while a program with init and step interpretations and sentences ψhalt\psi_{\mathrm{halt}} and ψout\psi_{\mathrm{out}} halts at the first stage hh with 𝔄h⊨ψhalt\mathfrak A_h\models\psi_{\mathrm{halt}}, and h+∑j≤h|V(𝔄j)|h+\sum_{j\le h}|V(\mathfrak A_j)| is polynomially bounded, the paper writing ρR\rho_R for ρt\rho_t.

What Is Checked

The definition is stated over finite structures over sets of binary relation symbols, the formulas of first-order logic with the Härtig quantifier with their satisfaction relation, and two-dimensional interpretations, applied to a structure by taking the pairs that satisfy δ\delta modulo the equivalence generated by η\eta.