Exponential state costs for two-way automata

What OpenAI claims

Proves exponential lower bounds both for complementing two-way nondeterministic finite automata and for simulating one-way nondeterministic automata by two-way deterministic ones. The latter resolves the Sakoda–Sipser state-succinctness conjecture over growing finite alphabets; both results rule out polynomial state bounds independent of alphabet size. (Lean)

Papers (2)

1. An exponential state lower bound for two-way nondeterministic complementation

   25 September 2026 · Preprint, not peer reviewed · PDF

   OpenAI's abstract We prove that two-way nondeterministic finite automata cannot be complemented with a polynomial number of states independent of the alphabet. For each n ≥ 4 we construct an n-state automaton over a finite alphabet whose complement requires at least 1/2 2^{⌊(n-4)/127⌋}-1 states.

2. An exponential two-way deterministic state lower bound for one-way liveness

   25 September 2026 · Preprint, not peer reviewed · PDF

   OpenAI's abstract One-way liveness on h points accepts a word of binary relations when their ordered product is nonempty. For every h ≥ 2, it has a nondeterministic automaton with h+3 states and no left moves, whereas every equivalent s-state two-way deterministic automaton satisfies 4(s+2)² ≥ 2^{⌊(h-2)/31⌋}. Partial transition rules, stay moves, and nonaccepting infinite computations are allowed. The alphabets are finite and grow with h, so the result rules out an alphabet-independent polynomial state bound for deterministic two-way simulation, already for one-way nondeterministic sources.

Status

Preprint. The papers have not been independently reviewed. Treat the result as OpenAI's claim until other mathematicians have checked it. If a video exists, it illustrates the statement; it is not the proof.