OctoInformBeta

OpenAI preprint, September 2026 Β· The direct lower bound for the BGS-style language (no numbered counterpart)

The direct lower bound and its variants: Programs and machines fail to decide the Gauss query within polynomial time and cumulative space; machines also fail with per-state space or when polynomially bounded

No choiceless polynomial time program with counting decides the Gauss 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), the model of Blass, Gurevich and Shelah, computes on a finite structure by building hereditarily finite sets over its elements, never choosing among them, within polynomially many steps and polynomially many active sets. A finite structure over a vocabulary Ο„\tau of eight binary relations presents a system of linear equations over the field 𝔽3\mathbb{F}_3, a system that Gaussian elimination solves in polynomial time, and the Gauss query QQ asks whether it has a solution.

Structures and the Gauss Query

The scalars are the elements of the field 𝔽3=β„€/3\mathbb{F}_3 = \mathbb{Z}/3.✦ The vocabulary Ο„\tau consists of the binary relation symbols Ed\mathrm{Ed}, Cf\mathrm{Cf}, EB\mathrm{EB}, VB\mathrm{VB}, II and one symbol ZΞ΄Z_\delta for each scalar Ξ΄\delta.✦ A Ο„\tau-structure SS on a finite set AA of atoms interprets each symbol of Ο„\tau as a binary relation on AA.✦ The configuration atoms of a Ο„\tau-structure SS on AA form the set X={a∈A:Cf(a,a)}X = \{a \in A : \mathrm{Cf}(a,a)\}, its edge atoms the set Y={y∈A:Ed(y,y)}Y = \{y \in A : \mathrm{Ed}(y,y)\}✦, and for t∈Xt \in X we write 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, written t∼yt \sim y, 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 of y∈Yy \in Y at a∈Xa \in X is the scalar Ξ³(y,a)=βˆ‘x∈Y,I(a,x)βˆ‘Ξ΄βˆˆπ”½3,ZΞ΄(y,x)Ξ΄.\gamma(y,a) = \sum_{x \in Y,\ I(a,x)} \ \sum_{\delta \in \mathbb{F}_3,\ Z_\delta(y,x)} \delta .(1)✦

Weights Ξ»:X→𝔽3\lambda \colon X \to \mathbb{F}_3 are normalized when they satisfy the first family of equations below✦, and they are consistent with weights ΞΌ:Y→𝔽3\mu \colon Y \to \mathbb{F}_3 when the second family holds: βˆ‘a∈XtΞ»(a)=1(t∈X),ΞΌ(y)=βˆ‘a∈XtΞ»(a)Ξ³(y,a)(t∈X,y∈Y,t∼y).\sum_{a \in X_t} \lambda(a) = 1 \quad (t \in X), \qquad \mu(y) = \sum_{a \in X_t} \lambda(a)\,\gamma(y,a) \quad (t \in X,\ y \in Y,\ t \sim y).(2)✦ The Gauss query QQ holds of SS, written Q(S)Q(S), when the linear system (2) in the unknowns Ξ»\lambda and ΞΌ\mu has a solution.✦

Hereditarily Finite Sets

The set HF(A)\mathrm{HF}(A) of hereditarily finite sets over a set AA of atoms is the smallest set that contains every atom of AA, as an urelement with no elements, and every finite set of its own members.✦ The rank of an atom and of the empty set 00 is 00, and the rank of any other set is one more than the largest rank of its elements.✦ The von Neumann ordinals are [0]=0[0] = 0 and [i+1]=[i]βˆͺ{[i]}[i+1] = [i] \cup \{[i]\}✦; the ordinal 1=[1]={0}1 = [1] = \{0\} is the truth value standing for true.✦ For finite AA, the set of all atoms Atoms∈HF(A)\mathrm{Atoms} \in \mathrm{HF}(A) has the atoms of AA as its elements.✦

The transitive closure of x∈HF(A)x \in \mathrm{HF}(A) and the closure of a finite family FβŠ†HF(A)F \subseteq \mathrm{HF}(A) are the finite sets tc(x)={x}βˆͺ⋃y∈xtc(y),tc(F)=⋃x∈Ftc(x).\mathrm{tc}(x) = \{x\} \cup \bigcup_{y \in x} \mathrm{tc}(y), \qquad \mathrm{tc}(F) = \bigcup_{x \in F} \mathrm{tc}(x).(3)

Machines and Their Runs

Fix a finite set of dynamic function symbols, each with an arity, and add the two control flags halt\mathrm{halt} and accept\mathrm{accept}, function symbols of arity 00. A location over AA is a symbol ff together with a tuple of members of HF(A)\mathrm{HF}(A) whose length is the arity of ff.✦ A state over AA assigns to every location a value in HF(A)\mathrm{HF}(A) such that only finitely many locations, its support, carry a value other than 00.✦ The critical sets Crit(s)\mathrm{Crit}(s) of a state ss are the values and the arguments of the locations in its support✦, and for finite AA its active sets form the finite set Act(s)=tc(Crit(s)βˆͺ{Atoms,0,1}βˆͺA).\mathrm{Act}(s) = \mathrm{tc}\bigl(\mathrm{Crit}(s) \cup \{\mathrm{Atoms}, 0, 1\} \cup A\bigr).(4)✦

Terms over Ο„\tau and these symbols are variables, the ordinals [n][n], the set Atoms\mathrm{Atoms} and applications f(t1,…,tk)f(t_1, \dots, t_k); from terms aa, bb and cc they further form the pair {a,b}\{a,b\}, the union ⋃a\bigcup a, the unique element of aa, the cardinality |a||a|, the tests a=ba = b, a∈ba \in b and β€œaa is an atom”, the input relation R(a,b)R(a,b) for RβˆˆΟ„R \in \tau, negation, conjunction, the conditional choosing aa or bb according to cc, and the comprehension {u(x):x∈a,g(x)}\{u(x) : x \in a,\ g(x)\}, which binds xx in its body uu and its guard gg.✦ Rules are skip\mathrm{skip}, updates f(t1,…,tk):=tf(t_1, \dots, t_k) := t, parallel compositions, conditionals, parallel loops forallx∈tdor\mathrm{forall}\ x \in t\ \mathrm{do}\ r and local definitions letx=tinr\mathrm{let}\ x = t\ \mathrm{in}\ r.✦ An operational machine PP over Ο„\tau consists of a finite set of dynamic function symbols with arities and one closed rule over them and the two flags, its body.✦

On a Ο„\tau-structure SS on a finite set AA, a store of PP is a state for its dynamic symbols and flags✦, and the run of PP is the sequence of stores s0,s1,…s_0, s_1, \dots, each possibly undefined, where s0s_0 gives every location the value 00 and sj+1s_{j+1} arises from sjs_j by one step of PP, which evaluates the body of PP in sjs_j and applies the resulting updates, and is undefined when sjs_j is or when these updates are inconsistent. A flag is raised in ss when ss gives it the value 11.✦ The machine halts at step hh when shs_h is defined and halt\mathrm{halt} is raised in it, and it accepts SS when for some hh both flags are raised in a defined shs_h.✦ The active sets of the run through step hh are Acth(P,S)=⋃j≀h,sj definedAct(sj).\mathrm{Act}_h(P,S) = \bigcup_{j \le h,\ s_j \text{ defined}} \mathrm{Act}(s_j).(5)✦

For numbers TT and WW, the machine accepts SS within time TT and cumulative space WW, written AccT,WΞ£(P,S)\mathrm{Acc}^{\Sigma}_{T,W}(P,S), when for some h≀Th \le T both flags are raised in a defined shs_h and |Acth(P,S)|≀W,|\mathrm{Act}_h(P,S)| \le W,(6)✦ and it accepts SS within time TT and space WW per state, written AccT,Wmax(P,S)\mathrm{Acc}^{\max}_{T,W}(P,S), when for some such hh |Act(sj)|≀Wfor every j≀h with sj defined.|\mathrm{Act}(s_j)| \le W \quad \text{for every } j \le h \text{ with } s_j \text{ defined}.(7)✦ For polynomials pp and qq with natural coefficients, polynomial cumulative acceptance is Accp(|A|),q(|A|)Ξ£\mathrm{Acc}^{\Sigma}_{p(|A|),q(|A|)}✦; for natural numbers cc and dd, cumulative cutoff acceptance and cutoff acceptance are AccT,WΞ£\mathrm{Acc}^{\Sigma}_{T,W} and AccT,Wmax\mathrm{Acc}^{\max}_{T,W} with T=W=c(|A|+1)dT = W = c(|A|+1)^d.

A machine PP over Ο„\tau is polynomially bounded when there are c,dβˆˆβ„•c, d \in \mathbb{N} such that on every Ο„\tau-structure SS on every finite set AA it halts at some step hh with h+|Acth(P,S)|≀c(|A|+1)d.h + |\mathrm{Act}_h(P,S)| \le c(|A|+1)^d.(8)✦

CPT Programs

A CPT program PP over Ο„\tau consists of a finite set of dynamic function symbols with arities and a rule over them and the two flags, its body; its terms and rules are formed by the clauses above, with disjunction added to the Boolean connectives.✦ Its stores, flags, run and active sets Acth(P,S)\mathrm{Act}_h(P,S) are defined as for machines. For polynomials pp and qq with natural coefficients, PP accepts SS within pp and qq when Accp(|A|),q(|A|)Ξ£(P,S)\mathrm{Acc}^{\Sigma}_{p(|A|),q(|A|)}(P,S) holds.✦ A query on finite Ο„\tau-structures is CPT-definable when some CPT program, with some polynomials pp and qq with natural coefficients, accepts within pp and qq exactly the structures that satisfy the query.✦

The Claim

Theorem 1. Throughout, SS is a Ο„\tau-structure on a finite set AA.

(a) The Gauss query QQ is not CPT-definable: for every CPT program PP and all polynomials pp and qq with natural coefficients there is a structure SS with Accp(|A|),q(|A|)Ξ£(P,S)⇎Q(S).\mathrm{Acc}^{\Sigma}_{p(|A|),\,q(|A|)}(P,S) \not\Leftrightarrow Q(S).(9)✦

(b) For every operational machine PP and all such polynomials pp and qq there is a structure SS with Accp(|A|),q(|A|)Ξ£(P,S)⇎Q(S).\mathrm{Acc}^{\Sigma}_{p(|A|),\,q(|A|)}(P,S) \not\Leftrightarrow Q(S).(10)✦

(c) For every operational machine PP and all c,dβˆˆβ„•c, d \in \mathbb{N} there is a structure SS with Accc(|A|+1)d,c(|A|+1)dΞ£(P,S)⇎Q(S).\mathrm{Acc}^{\Sigma}_{c(|A|+1)^d,\,c(|A|+1)^d}(P,S) \not\Leftrightarrow Q(S).(11)✦

(d) For every operational machine PP and all c,dβˆˆβ„•c, d \in \mathbb{N} there is a structure SS with Accc(|A|+1)d,c(|A|+1)dmax(P,S)⇎Q(S).\mathrm{Acc}^{\max}_{c(|A|+1)^d,\,c(|A|+1)^d}(P,S) \not\Leftrightarrow Q(S).(12)✦

(e) For every polynomially bounded operational machine PP there is a structure SS with P accepts S⇎Q(S).P \text{ accepts } S \not\Leftrightarrow Q(S).(13)✦

What Is Checked

The claims are stated over the Gauss query (2) on finite Ο„\tau-structures with scalars in 𝔽3\mathbb{F}_3, over hereditarily finite sets and their closures (3), over the states, active sets (4) and runs (5) of operational machines and of CPT programs, and over the acceptance conditions (6) and (7), the polynomial bound (8) and CPT-definability.