OctoInformBeta

OpenAI preprint, September 2026 · §5. Finite computations and the main lower bound · §5

§5 (proof of Theorem 1.1): For each n≥4n \ge 4, an nn-state two-way nondeterministic automaton over binary relations whose complement no ss-state one recognizes unless 2(s+1)≥2⌊(n−4)/127⌋2(s+1) \ge 2^{\lfloor (n-4)/127 \rfloor}

Complementing a two-way automaton can cost exponentially many states.

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

Let AA be a two-way nondeterministic finite automaton (2NFA) with nn states. How many states must a 2NFA have whose language is the complement of the language of AA, and can that number be forced to grow exponentially in nn? The automata here read words over the alphabet ℛH\mathcal{R}_H of binary relations on a finite set HH, and such a word multiplies out, letter by letter, to a single relation on HH.

The same question is asked of boundary diagrams, which record the paths that enter and leave a block from its left or right side. Diagrams on mm labels are assigned to the words over ℛH\mathcal{R}_H so that concatenation of words becomes the product of diagrams, and one pair of labels is to detect the words that multiply out to the empty relation: how large must mm be? A third statement concerns renaming the states of a 2NFA along a bijection.

Two-way Automata

A 2NFA AA over an alphabet Σ\Sigma with state set QQ consists of an initial state q0∈Qq_0 \in Q, a set F⊆QF \subseteq Q of accepting states and a transition function δ\delta, which assigns to each state qq and each tape symbol tt, a letter of Σ\Sigma or one of two distinct endmarkers ⊢{\vdash} and ⊣{\dashv} outside Σ\Sigma, a set δ(q,t)⊆Q×{−1,0,1}\delta(q, t) \subseteq Q \times \{-1, 0, 1\} of pairs of a next state and a head move, with −1-1, 00 and 11 standing for left, stay and right.✦

On a word w=w1⋯wkw = w_1 \cdots w_k over Σ\Sigma the tape has cells 0,1,…,k+10, 1, \dots, k+1, and cell ii holds the symbol ti={⊢if i=0,wiif 1≤i≤k,⊣if i=k+1,t_i = \begin{cases} {\vdash} & \text{if } i = 0,\\ w_i & \text{if } 1 \le i \le k,\\ {\dashv} & \text{if } i = k+1, \end{cases}(1)✦ so that the empty word is read as ⊢⊣{\vdash}{\dashv}. A configuration of AA on ww is a pair (q,i)(q, i) of a state and a cell. The one-step relation →w\to_w of AA on ww relates (q,i)(q, i) to (q′,i′)(q', i') when, for some move dd, (q′,d)∈δ(q,ti)andi′=i+d,(q', d) \in \delta(q, t_i) \quad\text{and}\quad i' = i + d,(2)✦ with i′i' again a cell of the tape.

The reflexive transitive closure P*P^* of a relation PP on a set XX is the relation on XX that relates xx to yy when there is a chain x=x0,x1,…,xj=yx = x_0, x_1, \dots, x_j = y, with j≥0j \ge 0, whose consecutive pairs lie in PP.✦ The language L(A)L(A) of AA is the set of words over Σ\Sigma on which a run of any length, zero included, leads from the initial state on the left endmarker to an accepting state: L(A)={w∈Σ*:(q0,0)→w*(q,i) for some q∈F and some cell i}.L(A) = \{\, w \in \Sigma^* : (q_0, 0) \to_w^* (q, i) \text{ for some } q \in F \text{ and some cell } i \,\}.(3)✦

The renaming e(A)e(A) of a 2NFA AA along a bijection e:Q→Q′e \colon Q \to Q' is the 2NFA over Σ\Sigma with state set Q′Q', initial state e(q0)e(q_0), accepting states e(F)e(F) and transition function δ′(q′,t)={(e(p),d):(p,d)∈δ(e−1(q′),t)}.\delta'(q', t) = \{\, (e(p), d) : (p, d) \in \delta(e^{-1}(q'), t) \,\}.(4)✦

Relations and Boundary Diagrams

Relations compose in path order: (x,z)∈PP′(x, z) \in PP' when (x,y)∈P(x, y) \in P and (y,z)∈P′(y, z) \in P' for some yy. The relation product r(w)r(w) of a word w=σ1⋯σkw = \sigma_1 \cdots \sigma_k over ℛH\mathcal{R}_H is the product σ1σ2⋯σk\sigma_1 \sigma_2 \cdots \sigma_k of its letters in ℛH\mathcal{R}_H, and r(ε)=IHr(\varepsilon) = I_H, the identity relation on HH.✦

A boundary diagram aa on mm labels is a quadruple of relations on two copies D+D^+ and D−D^- of an mm-element set of labels: the forward relation Fa⊆D+×D+F_a \subseteq D^+ \times D^+, whose edges enter on the left and exit on the right; the backward relation Ba⊆D−×D−B_a \subseteq D^- \times D^-, whose edges enter on the right and exit on the left; the left relation La⊆D+×D−L_a \subseteq D^+ \times D^-, whose edges enter and exit on the left; and the right relation Ra⊆D−×D+R_a \subseteq D^- \times D^+, whose edges enter and exit on the right.✦ These diagrams form the set 𝒯m\mathcal{T}_m.

The product abab of diagrams a,b∈𝒯ma, b \in \mathcal{T}_m is the diagram obtained by gluing aa to the left of bb, with relations composed in path order: Fab=Fa(LbRa)*Fb,Bab=Bb(RaLb)*Ba,Lab=La∪Fa(LbRa)*LbBa,Rab=Rb∪BbRa(LbRa)*Fb.\begin{aligned} F_{ab} &= F_a (L_b R_a)^* F_b, & B_{ab} &= B_b (R_a L_b)^* B_a,\\ L_{ab} &= L_a \cup F_a (L_b R_a)^* L_b B_a, & R_{ab} &= R_b \cup B_b R_a (L_b R_a)^* F_b. \end{aligned}(5)✦ The identity diagram 1m∈𝒯m1_m \in \mathcal{T}_m is the diagram with forward relation ID+I_{D^+}, backward relation ID−I_{D^-}, and empty left and right relations.✦

The loss bound of a natural number hh is D(h)=2⌊(h−2)/127⌋.D(h) = 2^{\lfloor (h-2)/127 \rfloor}.(6)✦

The Claim

Theorem 1. Let n≥4n \ge 4 and H={1,…,n−2}H = \{1, \dots, n-2\}. There is a 2NFA AA over ℛH\mathcal{R}_H with nn states such that every 2NFA BB over ℛH\mathcal{R}_H with ss states and L(B)=ℛH*\L(A)L(B) = \mathcal{R}_H^* \setminus L(A) satisfies 2⌊(n−4)/127⌋≤2(s+1).2^{\lfloor (n-4)/127 \rfloor} \le 2(s+1).(7)✦

Theorem 2. Let h≥2h \ge 2 and m≥1m \ge 1, let HH be a set with hh elements, and let τ\tau map the words over ℛH\mathcal{R}_H to diagrams in 𝒯m\mathcal{T}_m so that τ(ε)=1m\tau(\varepsilon) = 1_m and τ(uv)=τ(u)τ(v)\tau(uv) = \tau(u)\,\tau(v) for all words uu and vv. Suppose that for some diagrams λ,ρ∈𝒯m\lambda, \rho \in \mathcal{T}_m and labels α,β\alpha, \beta, every word ww over ℛH\mathcal{R}_H has (α,β)∈F(λτ(w))ρ(\alpha, \beta) \in F_{(\lambda\tau(w))\rho} if and only if r(w)=∅r(w) = \emptyset. Then D(h)≤2m.D(h) \le 2m.(8)✦

Theorem 3. Let AA be a 2NFA over Σ\Sigma with state set QQ, and let e:Q→Q′e \colon Q \to Q' be a bijection. Then L(e(A))=L(A).L(e(A)) = L(A).(9)✦

What Is Checked

The three claims are stated over the 2NFA with its tape between endmarkers (1), its one-step relation (2) and its language (3) through the reflexive transitive closure, the renaming of states (4), the relation product rr on words over ℛH\mathcal{R}_H, the boundary diagrams in 𝒯m\mathcal{T}_m with their product (5) and the identity 1m1_m, and the loss bound (6).