The Sakoda and Sipser problem

Abstract

It is well known that finite automata accept exactly the class of regular languages, across all standard variants: deterministic and nondeterministic, as well as one-way and two-way models. In the one-way setting, eliminating nondeterminism incurs an exponential blow-up in the size of the automaton.
In 1978, Sakoda and Sipser posed the question of whether nondeterminism in one-way and two-way finite automata can be eliminated at polynomial cost by exploiting the ability of two-way deterministic finite automata to scan the input in both directions.
 
This talk explores the Sakoda–Sipser conjecture, discusses why these problems are difficult, and highlights their connections to the P vs NP question.