State complexity of simulating one-way NFAs by two-way DFAs

Can every small one-way nondeterministic finite automaton be simulated by a polynomial-size two-way deterministic automaton independently of alphabet size? The target family has h+3 NFA states and forces 2^⌊(h−2)/31⌋≤4(s+2)² for a two-way DFA with s states; its alphabet grows with h.

Why it matters and what counts as progress

Why it matters: It asks whether two-way deterministic motion can remove the state cost of one-way nondeterminism without an alphabet restriction.

What counts as progress: A superpolynomial state lower bound for equivalent two-way deterministic automata, with alphabet growth specified, or a stronger simulation theorem.

How the problem developed

1978 · Open question [1]
William J. Sakoda and Michael Sipser Asked how many states a two-way deterministic finite automaton needs to simulate a one-way nondeterministic finite automaton, conjecturing exponential cost.
25 Sept 2026 · Lower bound claim [2]
OpenAI Reported an exponential lower bound for two-way DFAs simulating a family of one-way NFAs recognizing liveness of products of binary relations, over a finite alphabet growing with the parameter.

AI contribution

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

OpenAI

For each h≥2, an h+3-state one-way nondeterministic automaton recognizes liveness of products of binary relations, while every equivalent two-way deterministic automaton with s states satisfies 2^⌊(h−2)/31⌋≤4(s+2)². The finite alphabet grows with h.

AI involvementAI-led

ImportanceMajor

Technical verificationFormal (Lean 4 formalization with OneWayLiveness Comparator)

Human understandingFew