OctoInformBeta

OpenAI preprint, September 2026 · §1. Introduction · §1

Theorem 1.1 [Main theorem]: For every n≥4n \ge 4, an nn-state automaton over the relations on n−2n-2 points whose complement needs at least 12⋅2⌊(n−4)/127⌋−1\tfrac12 \cdot 2^{\lfloor (n-4)/127 \rfloor} - 1 states

Complementing two-way nondeterministic automata can need 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 over a finite alphabet Σ\Sigma, reading its input between a left and a right endmarker. How many states does a 2NFA need to recognize the complement Σ*\L(A)\Sigma^* \setminus L(A), as a function of nn? In particular, is there a polynomial pp such that every nn-state 2NFA, over any finite alphabet, has a 2NFA with at most p(n)p(n) states for its complement?

The library answers with a family of witnesses over alphabets that grow with nn: for each n≥4n \ge 4, a 2NFA with nn states over the alphabet of binary relations on a set of n−2n - 2 points, and a lower bound on the number of states of every 2NFA over that alphabet that recognizes the complement of its language.

Two-way Automata

A two-way nondeterministic finite automaton AA over an alphabet Σ\Sigma, with a set QQ of states, consists of an initial state q0∈Qq_0 \in Q, a set F⊆QF \subseteq Q of accepting states and a transition function δ\delta that assigns to each state qq and each tape symbol a∈Σ∪{⊢,⊣}a \in \Sigma \cup \{{\vdash}, {\dashv}\}, where ⊢\vdash is the left endmarker and ⊣\dashv the right endmarker, a set δ(q,a)⊆Q×{−1,0,+1}\delta(q, a) \subseteq Q \times \{-1, 0, +1\} of pairs of a next state and a head move, left, stay or right.✦

On an input w=w1⋯wm∈Σ*w = w_1 \cdots w_m \in \Sigma^* the tape has the cells 0,1,…,m+10, 1, \dots, m+1, and the tape symbol tw(i)t_w(i) at cell ii is tw(0)=⊢,tw(i)=wi(1≤i≤m),tw(m+1)=⊣.t_w(0) = {\vdash}, \qquad t_w(i) = w_i \quad (1 \le i \le m), \qquad t_w(m+1) = {\dashv}.(1)✦

A configuration of AA on ww is a pair (q,i)(q, i) of a state q∈Qq \in Q and a cell ii of the tape. The one-step relation →w\to_w of AA on ww is the relation on configurations given by (q,i)→w(q′,i′)⇔(q′,i′−i)∈δ(q,tw(i)),(q, i) \to_w (q', i') \iff (q', i' - i) \in \delta\bigl(q, t_w(i)\bigr),(2)✦ and its reflexive transitive closure →w*\to_w^* relates a configuration cc to a configuration c′c' when there is a run c=c0→wc1→w⋯→wck=c′c = c_0 \to_w c_1 \to_w \cdots \to_w c_k = c' of some length k≥0k \ge 0.

The language L(A)⊆Σ*L(A) \subseteq \Sigma^* recognized by AA consists of the words on which a run from the initial configuration (q0,0)(q_0, 0) reaches 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)✦

Relations as Letters

For a set HH, the relation monoid ℛH\mathcal{R}_H is the monoid of binary relations on HH under the path-order product, in which, for relations a,ba, b on HH, (x,z)∈ab(x, z) \in ab when (x,y)∈a(x, y) \in a and (y,z)∈b(y, z) \in b for some y∈Hy \in H, with the identity relation IHI_H as its unit.

For a word w=a1⋯amw = a_1 \cdots a_m over the alphabet ℛH\mathcal{R}_H, the relation product r(w)r(w) is the element of ℛH\mathcal{R}_H r(w)=a1a2⋯am,r(ε)=IH.r(w) = a_1 a_2 \cdots a_m, \qquad r(\varepsilon) = I_H.(4)✦ The language LHL_H over ℛH\mathcal{R}_H is the set of words whose relation product is nonempty: LH={w∈ℛH*:r(w)≠∅}.L_H = \{\, w \in \mathcal{R}_H^* : r(w) \neq \emptyset \,\}.(5)✦

The Claim

Theorem 1. Let Σn\Sigma_n be the alphabet ℛH\mathcal{R}_H with H={1,…,n−2}H = \{1, \dots, n-2\}.

  1. For every n≥4n \ge 4 there is a 2NFA AnA_n over Σn\Sigma_n with nn states such that, for every 2NFA over Σn\Sigma_n with a finite set QQ of states that recognizes Σn*\L(An)\Sigma_n^* \setminus L(A_n), both of the following hold: L(An)=LHand|Q|≥12⋅2⌊(n−4)/127⌋−1.L(A_n) = L_H \qquad\text{and}\qquad |Q| \ge \tfrac{1}{2} \cdot 2^{\lfloor (n-4)/127 \rfloor} - 1.(6)✦

  2. For every n≥4n \ge 4 there is a 2NFA AnA_n over Σn\Sigma_n with nn states such that every 2NFA over Σn\Sigma_n with ss states that recognizes Σn*\L(An)\Sigma_n^* \setminus L(A_n) satisfies 2⌊(n−4)/127⌋≤2(s+1).2^{\lfloor (n-4)/127 \rfloor} \le 2(s+1).(7)✦

  3. For every n≥4n \ge 4 there is a 2NFA AnA_n over Σn\Sigma_n with nn states such that every 2NFA over Σn\Sigma_n with a finite set QQ of states that recognizes Σn*\L(An)\Sigma_n^* \setminus L(A_n) satisfies |Q|≥12⋅2⌊(n−4)/127⌋−1.|Q| \ge \tfrac{1}{2} \cdot 2^{\lfloor (n-4)/127 \rfloor} - 1.(8)✦

  4. For every polynomial pp with real coefficients there are natural numbers nn and kk and a 2NFA AA with nn states over the alphabet Σ={1,…,k}\Sigma = \{1, \dots, k\} such that every 2NFA over Σ\Sigma with ss states that recognizes Σ*\L(A)\Sigma^* \setminus L(A) satisfies s>p(n).s > p(n).(9)✦

In the paper, the result reads: for every integer n≥4n \ge 4, with H={1,…,n−2}H = \{1, \dots, n-2\} and Σn=ℛH\Sigma_n = \mathcal{R}_H, there is an nn-state 2NFA AnA_n recognizing LHL_H such that every 2NFA recognizing Σn*\L(An)\Sigma_n^* \setminus L(A_n) has at least 12⋅2⌊(n−4)/127⌋−1\tfrac12 \cdot 2^{\lfloor (n-4)/127 \rfloor} - 1 states, and in particular there is no polynomial state bound for complementation that is independent of the finite alphabet.

What Is Checked

The four claims are stated over two-way nondeterministic automata with endmarkers and their languages (3), defined by runs of the one-step relation (2) on the tape (1): (6), (7) and (8) over the alphabet ℛH\mathcal{R}_H, (6) also over the language LHL_H of (5) and the relation product (4), and (9) over the alphabets {1,…,k}\{1, \dots, k\}.