The Sakoda-Sipser problem: exponential cost of simulating nondeterministic automata by two-way deterministic ones

For every $h\ge2$, one-way liveness $\mathrm{OWL}_h$ has a nondeterministic automaton with $h+3$ states and no left moves, while every equivalent 2DFA with $s$ states satisfies $4(s+2)^2\ge2^{\lfloor(h-2)/31\rfloor}$. Hence no polynomial $Cn^c$ bounds 1NFA-to-2DFA (and so 2NFA-to-2DFA) conversion uniformly over finite alphabets. The deterministic target is unrestricted (stay moves, partial rules, infinite rejecting runs). The companion gives the weaker-rate bound $\tfrac12 2^{\lfloor(n-4)/127\rfloor}$ for the same family. Not shown: any lower bound over a fixed alphabet (e.g. binary), any bound in transition-table size, or anything about L versus NL.

For every $h\ge2$, one-way liveness $\mathrm{OWL}_h$ has a nondeterministic automaton with $h+3$ states and no left moves, while every equivalent 2DFA with $s$ states satisfies $4(s+2)^2\ge2^{\lfloor(h-2)/31\rfloor}$. Hence no polynomial $Cn^c$ bounds 1NFA-to-2DFA (and so 2NFA-to-2DFA) conversion uniformly over finite alphabets. The deterministic target is unrestricted (stay moves, partial rules, infinite rejecting runs). The companion gives the weaker-rate bound $\tfrac12 2^{\lfloor(n-4)/127\rfloor}$ for the same family. Not shown: any lower bound over a fixed alphabet (e.g. binary), any bound in transition-table size, or anything about L versus NL.