Exponential state costs for two-way automata

Removing guesses from simple two-way reading machines can cost exponentially many states.

2 papers September 25, 2026 Explained by AI

A finite automaton is a tiny machine that reads a word letter by letter using a fixed number of states. A guessing machine can check whether a chain of relations leaves some path alive using few states. The second paper proves that a machine without guesses needs exponentially many states for this. That holds even if it may reread the input. The first paper proves that a guessing machine that confirms no path exists also needs exponentially many states.

First step

1978

Sakoda and Sipser, who posed the state-cost question

Significance

Major

It replaces a quadratic lower bound with an exponential one for unrestricted two-way deterministic machines, over growing alphabets.

Trust

Formal proof listed

Field

Theoretical computer science

2 papers

The explanation

Take three points, called 1, 2 and 3. A relation here is a list of allowed one-step moves between them. Read three relations in order: 1 to 2, then 2 to 3, then 3 to 1. Chaining them gives a path from 1 back to 1. So this word is live: at least one path survives every step. Now swap the last relation for the single move 1 to 1. No step leaves point 3 anymore, so the chain is empty and the word is dead. Telling live words from dead ones is a task called one-way liveness.

The papers ask how big a simple machine must be to do this task. The machine is a finite automaton. It has a fixed number of internal modes, called states, and a head that reads one letter at a time. Here every possible relation is one letter. On 3 points there are 2 to the power 9, or 512, letters. A nondeterministic machine may guess its next move and accepts if some guess works. Guessing makes liveness easy: guess a path and check each step. For h points, one such machine uses h + 3 states and never moves its head left.

A deterministic machine cannot guess. Each state and letter fix its one next move. A two-way machine may move its head back and reread letters. Rabin, Scott and Shepherdson showed in 1959 that two-way deterministic machines recognize the same languages as one-way machines. The open question was the price in states. Sakoda and Sipser posed this question in 1978. Is there a polynomial rule, such as n squared, for removing guesses?

Earlier lower bounds all limited how the deterministic machine moves. Sipser proved an exponential gap in 1980 for sweeping machines, which turn around only at the ends of the input. Kapoutsis extended this in 2013 to machines with few turns. Against unrestricted machines, the best bound was quadratic, from Adeogun and Kapoutsis in 2026. The obstacle is that an unrestricted machine can turn anywhere and revisit a letter many timesSource 1. The second paper handles this by turning each letter into a fixed wiring pattern. That pattern depends only on the letter, not on its neighbours.

Its main theorem gives a hard number. Take h = 2000 points. The guessing machine needs only 2003 states. Every deterministic two-way machine for the same task needs at least 2,147,483,646 states, about 2.1 billionSource 2. In general, a machine with s states must satisfy 4(s+2)^2 ≥ 2^⌊(h−2)/31⌋. The needed size grows exponentially with h. So no polynomial rule can turn every guessing machine into a deterministic two-way oneSource 3.

The first paper asks a related question about complements. The complement of a task swaps its yes and no answers. Here it means recognizing dead words, where the chain is empty. For deterministic two-way machines, complementing costs only a linear number of extra statesSource 4. Vardi showed in 1989 how to complement a guessing two-way machine with exponentially many states. Guillon, Prigioniero and Taheri describe polynomial complementation of such machines as open. The first paper says it is not possible. It builds an n-state guessing machine for liveness. Any guessing machine for dead words then needs at least ½·2^⌊(n−4)/127⌋ − 1 statesSource 5. For n = 4000, that is 1,073,741,823 states, about 1.07 billion. Guessing a path is cheap, but a guessing machine cannot cheaply confirm that no path exists.

Both results need a condition that is easy to miss. The alphabet grows with the problem. On h points there are 2 to the power h squared lettersSource 6. The papers rule out a polynomial rule that holds for every alphabet. They give no lower bound over one fixed alphabetSource 7. The bounds also start slowly. For n = 131, the complement formula gives zero. They say nothing about logarithmic-space complexity classes, which concern machines with a work tapeSource 8.

How sure is this? The Lean scope note lists Lean formalizations of all three bounds. A computer proof checker called Lean covers the complement bound for every n ≥ 4. It also covers the same family's deterministic bound for n ≥ 131. It covers the liveness bound for every h ≥ 2. Each has a Comparator statement, a fixed reference version used for matching. No specialist review has been published.

What it doesn't show. This does not give a lower bound for machines over one fixed alphabet, and it separates no logarithmic-space complexity classes.

Where it came from

This result comes from an unreleased OpenAI model, published in the openai/math release on 6 October 2026.

Hype check

Major if the formal statements say what the papers claim. The scope note lists Lean formalizations of the three bounds, but they hold only for alphabets that grow. No specialist review has been published.

Words used

Finite automaton: A simple machine with a fixed number of states that reads a word one letter at a time.
State: One of the machine's fixed internal modes; the count of states measures the machine's size.
Nondeterministic: Allowed to guess its next move; it accepts if at least one sequence of guesses succeeds.
Deterministic: Has exactly one possible next move at each step, so no guessing.
Two-way: Able to move its reading head left as well as right and reread letters.
One-way liveness: The task of deciding whether a chain of relations still allows at least one complete path.
Complement: The task with yes and no answers swapped.
Alphabet: The set of letters a machine can read; here it grows as the number of points grows.

The original papers (2)

An exponential state lower bound for two-way nondeterministic complementation (PDF, opens in a new tab)
September 25, 2026 Formal proof listed
An exponential two-way deterministic state lower bound for one-way liveness (PDF, opens in a new tab)
September 25, 2026 Formal proof listed

Lean notes

All quoted lines (8)

The main representation difficulty is to account for repeated visits to a cell while assigning each input symbol a fixed object independent of its neighbors.
An exponential two-way deterministic state lower bound for one-way liveness Back to text
For every integer $h\ge2$ , the language $\OWL_h$ is recognized by a nondeterministic automaton with $h+3$ states using no left moves. Every equivalent deterministic two-way automaton with $s$ states satisfies $4(s+2)^2\ge 2^{\lfloor(h-2)/31\rfloor}.$
An exponential two-way deterministic state lower bound for one-way liveness Back to text
There are no absolute constants $C,c>0$ such that every $n$ -state two-way nondeterministic automaton over every finite alphabet has an equivalent two-way deterministic automaton with at most $Cn^c$ states.
An exponential two-way deterministic state lower bound for one-way liveness Back to text
For deterministic two-way automata, complementation has a linear state bound independent of the alphabet.
An exponential state lower bound for two-way nondeterministic complementation Back to text
For every integer $n\ge4$ , set $H=\{1,\ldots,n-2\}$ and $\Sigma_n=\mathcal R_H$ . There is an $n$ -state 2NFA $A_n$ recognizing $L_H$ such that every 2NFA recognizing $\Sigma_n^*\setminus L(A_n)$ has at least $\frac12\,2^{\lfloor(n-4)/127\rfloor}-1$ states.
An exponential state lower bound for two-way nondeterministic complementation Back to text
This bound exceeds $Cn^c$ for every fixed $C,c$ when $n$ is large enough. For each $h$ the alphabet has $2^{h^2}$ symbols and is finite.
An exponential two-way deterministic state lower bound for one-way liveness Back to text
Theorem … concerns bounds uniform over finite alphabets; it does not assert a lower bound over one fixed alphabet.
An exponential state lower bound for two-way nondeterministic complementation Back to text
They compare finite-state machines without a work tape, and give no separation between uniform logarithmic-space complexity classes.
An exponential state lower bound for two-way nondeterministic complementation Back to text