Exponential state costs for two-way automata

Source and verification

This article explains family 129 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Finite automata and relation products

A two-way finite automaton reads a word between two endmarkers. Its memory consists of a state and the position of one read-only head. Each transition changes the state and moves the head left, right, or not at all. A deterministic machine has at most one successor from each state-symbol pair; a nondeterministic machine may choose among several. A word is accepted if some finite computation reaches an accepting state. An infinite computation that never accepts does not accept.

The resource studied here is the number of states, including initial and accepting states. Neither input length nor computation time is bounded. There are no writable cells, extra heads, random bits, or advice.

Let $H=\{1,\dots ,h\}$, with $h\ge 2$. A binary relation on $H$ is a set of directed edges between two copies of $H$. Compose relations in path order:

$$\begin{array}{c}(i,k)\in AB⟺\\ \exists j:(i,j)\in A,(j,k)\in B.\end{array}$$

Use the collection of all relations on $H$ as an alphabet. A word $w=R_1\cdots R_{\ell }$ describes a layered directed graph, and its product $r(w)$ records which initial vertices can reach which final vertices. Define the one-way liveness language

$$L_H=\{w:r(w)\ne \varnothing \}.$$

The empty product is the identity relation $I_H$, so the empty word belongs to $L_H$.

For example, with $H=\{1,2\}$, take $A=\{(1,2)\}$ and $B=\{(2,1)\}$. Then $AB=\{(1,1)\}$, so $AB$ is live, whereas $AA$ has empty product. Individual nonempty letters need not form a live word.

A small nondeterministic recognizer guesses an initial vertex and then a path through the layers. It uses $h$ path states, an initial state, and an accepting state. At a relation letter it follows one allowed edge; at the right marker it accepts. Missing transitions reject the current branch. Thus $h+2$ states suffice, without any left moves. Adding an explicit rejecting sink gives the companion paper’s $h+3$-state construction. (OpenAI, 2026) (OpenAI, 2026b)

🏷️ Two exponential state bounds

Complementation and determinization, as stated in the manuscripts

Every two-way nondeterministic recognizer of the complement of $L_H$ has at least

$$\frac{1}{2}{2}^{\lfloor (h-2)/127\rfloor }-1$$

states. Independently, every deterministic two-way recognizer of $L_H$, with $s$ states, satisfies

$$4(s+2{)}^2\ge 2^{\lfloor (h-2)/31\rfloor }.$$

When an accepting initial configuration counts as acceptance, the second bound improves to $4(s+1{)}^2$ on the left. (OpenAI, 2026a) (OpenAI, 2026b)

The first theorem says that even a nondeterministic machine cannot recognize absence of a path with polynomially many states in this family. The second concerns deterministic recognition of the original path-existence language and gives a stronger exponential rate for that task.

There are $2^{h^2}$ alphabet symbols. These conclusions exclude polynomial state bounds whose constants are independent of the finite alphabet. They do not establish the same bounds over one fixed alphabet, and they are not lower bounds in terms of transition-table description length. Nor do they separate uniform logarithmic-space complexity classes: the parameter and computational model are different.

Complementing a deterministic machine also requires care. Exchanging accepting and rejecting states does not handle an infinite nonaccepting computation. The complementation paper invokes a separate linear-state deterministic complementation theorem that handles this issue; the companion’s direct proof avoids relying on that consequence for its sharper bound.

🏷️ Boundary summaries and context tests

A two-way computation may cross a cut many times. Recording only the state on its first crossing therefore loses information. The complementation paper instead summarizes an interval by four relations:

• entries from the left that can exit on the right;
• entries from the right that can exit on the left;
• entries from the left that can return to the left;
• entries from the right that can return to the right.

Boundary labels contain a state and a direction. Gluing two interval diagrams permits arbitrary finite alternation across the shared boundary. This gives an associative composition because expanding or contracting interval paths preserves finite reachability. Adding edges to a diagram can only add possible computations.

Stay moves are included exactly: inside a cell, take any finite sequence of stay transitions, followed by an exit move. An auxiliary success state turns acceptance into a designated rightward exit. This representation uses $s+1$ labels in each direction for an $s$-state machine. It preserves finite acceptance even when other branches loop indefinitely. (OpenAI, 2026a)

The full relation alphabet provides particularly strong tests. Put $I_i=\{(i,i)\}$. For any relation $A$,

$$I_{i}A{I}_j=\{\begin{array}{ll}\{(i,j)\},& (i,j)\in A,\\ \varnothing ,& (i,j)\notin A.\end{array}$$

Thus placing two singleton letters around a word tests any chosen entry of its relation product.

Suppose two words have the same computation diagram. Every surrounding context then produces the same acceptance decision. If their relation products differed, a singleton context would distinguish them. Consequently, the relation product is a well-defined function of the diagram. Every relation occurs as a one-letter word, so this function reaches all relations and respects concatenation.

For a machine recognizing emptiness, there is more information. Write $D(u)\subseteq D(v)$ when each boundary relation of the first diagram is contained in that of the second. If $(i,j)$ is absent from $r(u)$, the emptiness machine accepts $I_{i}u{I}_j$. Monotonicity of diagram paths implies acceptance of $I_{i}v{I}_j$, so $(i,j)$ is absent from $r(v)$ as well. Therefore

$$\begin{array}{c}D(u)\subseteq D(v)⟹\\ r(v)\subseteq r(u).\end{array}$$

This reversal of inclusion is the precise input to the paper’s finite-diagram lower bound. Counting all possible diagrams would not establish the needed exponential number of boundary labels.

🏷️ Amplifying a loss of boundary information

The remaining complementation argument is a structural theorem about these finite path diagrams. Its conclusion is that an inclusion-reversing representation of all relations on $h$ points, with $m$ labels in each direction, must satisfy

$$2m\ge 2^{\lfloor (h-2)/127\rfloor }.$$

Substituting $m=s+1$ yields the first automata bound.

The mechanism tracks recurrent classes of boundary labels under a diagram that is unchanged by composition with itself. Restricting attention to diagrams stabilized on both sides by that diagram creates a smaller setting in which the induction can continue. Some operations destroy loops on recurrent classes; those lost classes form a finite budget.

Two estimates are essential. Transport through a fixed surrounding context increases a common loss budget by at most a constant factor. Along a nested sequence of such restrictions, the sum of the successive losses is also controlled by one initial budget. Without the latter estimate, the same destroyed information could be charged afresh at every stage.

The amplification arranges $2t$ relabeled copies of one relation modification so that they induce $t^2$ additions. Each addition contains a smaller instance of the original representation problem. With $t=64$, comparing the total required loss with the shared budget produces the exponential recurrence and the decrement $127$ in $h$. These transport and nested-loss estimates are substantive source theorems; the elementary context argument alone does not prove them. (OpenAI, 2026a)

🏷️ Deterministic computations as matching diagrams

The deterministic companion uses perfect matchings between boundary ports rather than four arbitrary reachability relations. The reason determinism helps is a simple fact about a finite directed graph in which every vertex has at most one successor.

Sink component lemma

If $t$ has no successor, its connected component in the underlying undirected multigraph consists exactly of the vertices whose successor paths reach $t$. That component is a tree.

To prove this, let $B$ be the set of vertices reaching $t$. Along any successor edge $u\to v$, membership in $B$ is equivalent at the two endpoints. Hence $B$ is the component of $t$. Every vertex there except $t$ has exactly one outgoing edge, so the connected component with $v$ vertices has $v-1$ edges and is a tree. Nonaccepting cycles lie elsewhere.

After routing acceptance to a designated sink, a tour of this tree can encode acceptance by whether two test ports are connected. Choose a cyclic ordering of incidences at each vertex; on arriving along an edge, leave along the next incidence. On a tree this visits each directed edge traversal in one cycle. Removing a leaf and then reinserting its out-and-back excursion proves the assertion inductively. Cutting the tour at two designated leaves gives two paths connecting the cuts.

A further issue is locality: the diagram assigned to a letter must not depend on its neighbors. The construction reserves a slot for each direction and ordered pair of states. The target end of a slot always attaches to the designated target state. At the source end, an actual transition attaches to its source state; an unused candidate attaches to its own separate leaf. This changes neither connectivity between state vertices nor the sink-tree property. Two lanes per slot give $4(s+1{)}^2$ boundary ports. (OpenAI, 2026b)

Singleton contexts again imply that the generated matching diagrams represent every relation product faithfully. The companion’s structural theorem then forces at least $2^{\lfloor (h-2)/31\rfloor }$ ports.

Here the loss variable is matching rank: the number of pairs joining opposite boundaries. Restriction to an idempotent diagram of rank $r$ reduces the problem to $r$ ports, with control of one common support set. The amplification uses $32$ relabeled diagrams to generate $256$ relation additions; each addition contains a problem on $h-31$ points. The common support budget prevents these additions from being paid for independently. This gives the second exponential recurrence. Its finite-diagram proof is distinct from the nondeterministic recurrent-class argument.

🏷️ Key steps and proof outlines

A relation alphabet makes contextual tests exact

Let $H$ be an $h$-element set, and regard each input letter as a binary relation on $H$. The product of a word records all possible paths through its letters. For $i\in H$, write $I_i=\{(i,i)\}$. Then $I_{i}R{I}_j$ is nonempty exactly when $(i,j)\in R$. Thus every individual entry of a relation can be tested by a left and right context. This elementary observation prevents a boundary summary from identifying two relations merely because they agree on the current acceptance test.

For a nondeterministic complementing machine, enlarging its boundary reachability diagram can only add accepting paths. Since acceptance here means that the original relation product is empty, the induced relation map reverses inclusion: more boundary paths must correspond to fewer surviving relation pairs. The lower bound consequently needs an order-reversing diagram theorem, not a bound on the number of arbitrary summaries. Deterministic machines instead yield matching diagrams with a rank invariant. These are distinct structural inputs even though the amplification pattern is shared. (OpenAI, 2026a; OpenAI, 2026b)

Amplifying one defect through a hub

Here is the quantitative mechanism in “An exponential bound for order-reversing images.” For an idempotent boundary diagram $e$, its recurrent classes are the persistent components under repeated composition. Write ${\mathcal{M}}_e(a)$ for the classes missing after inserting a diagram $a$, and let $c=|{\mathcal{M}}_e(a)|$ when its relation image is the identity plus one off-diagonal pair. The proof seeks a lower bound on $c$.

Choose disjoint sets $U=\{u_1,\dots ,u_t\}$ and $V=\{v_1,\dots ,v_t\}$ and a hub $z$. Relabeling the original pair supplies $2t$ diagrams whose relation images add $u_i\to z$ or $z\to v_j$. Multiplying one of each and restricting away from $z$ gives a diagram adding exactly $u_i\to v_j$. Thus only $2t$ initial defects generate $t^2$ distinguishable additions.

The common-set transport lemma charges all these operations to one missing-class set, rather than charging the same class separately at every step. After transport its size is at most $8tc$. Enumerate the $t^2$ pairs and successively add them, taking idempotent powers after each insertion. No new two-step paths are created among these added edges because $U\cap V=\varnothing$. If ${\delta }_{\ell }$ is the loss at the $\ell$th nested step, the chain inequality gives

$$\sum _{\ell =1}^{t^2}{\delta }_{\ell }\le 16tc.$$

Every step contains a smaller hard instance

To lower-bound a particular ${\delta }_{\ell }$, retain only the newly added pair’s two endpoints and the points outside $U\cup V\cup \{z\}$. The retained set has $h-2t+1$ elements. Before this step, its restricted relation is the identity; after the step, it contains the chosen additional pair. The restricted diagrams must still represent all relations on the smaller set, or induction would not apply.

The source ensures this by taking a minimal idempotent preimage of the restricted identity. Sandwiching by that idempotent produces a smaller domain with the correct identity and a surjective relation map. A finite-power argument supplies invertible lifts of relabelings: an element mapping to an invertible relation has an idempotent power, and minimality forces that power to be the domain identity. This verifies the symmetry hypothesis again inside the restricted problem.

Transport into this smaller domain loses at most a factor two. If $D(h)$ is the inductive lower bound, then $2{\delta }_{\ell }\ge D(h-2t+1)$. Combining all steps yields

$$16tc\ge \frac{t^2}{2}D(h-2t+1),c\ge \frac{t}{32}D(h-2t+1).$$

Taking $t=64$ gives $D(h)=2D(h-127)$, with base value one, hence $D(h)=2^{\lfloor (h-2)/127\rfloor }$. Since a width-$m$ diagram has at most $2m$ recurrent classes, $D(h)\le 2m$, which converts to the stated state lower bound. The exponential growth comes from quadratic amplification against a linear shared budget.

Why the deterministic exponent is different

The deterministic companion uses the same hub construction with $t=16$, but measures rank loss rather than missing recurrent classes. Its shared support budget is $4tc$, while each of the $t^2$ additions costs at least half the smaller-instance bound $L(h-2t+1)$. Therefore $64c\ge 128L(h-31)$ and $L(h)=2^{\lfloor (h-2)/31\rfloor }$. The separate machine-to-matching construction has width bounded by $4(s+2{)}^2$ for an $s$-state machine, giving the quadratic prefactor in its final inequality. Neither the improved decrement $31$ nor that width conversion can be transferred automatically to the nondeterministic proof. (OpenAI, 2026b)

🏷️ Reading connections

Depth-three circuit lower bounds studies a different restricted computational resource: gates rather than finite states. The common lesson is to specify the allowed computations before comparing lower bounds. The constructions here allow unlimited head motion and computation time while keeping finite control small.

🏷️ Manuscripts and verification scope

• An exponential state lower bound for two-way nondeterministic complementation — pinned manuscript and companion source.
• An exponential two-way deterministic state lower bound for one-way liveness — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. Its comparator list covers both the nondeterministic complementation bound and the direct liveness determinization bound, with their distinct state offsets and growing-alphabet conventions. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026a. An exponential state lower bound for two-way nondeterministic complementation.

🐻  OpenAI 2026b. An exponential two-way deterministic state lower bound for one-way liveness.