Two-way automata characterizations of L/poly versus NL (Q2354593)

As the authors note in the introduction, ``A prominent open question in complexity theory asks whether nondeterminism is essential in logarithmic-space Turing machines. Formally, this is the question whether \(\mathrm{L}=\mathrm{NL}\), for \(\mathrm{L}\) and \(\mathrm{NL}\) the standard classes of languages recognizable by logarithmic-space deterministic and nondeterministic Turing machines. In the late 70s, Berman and Lingas connected this question to the comparison between deterministic and nondeterministic two-way finite automata (2DFAs and 2NFAs), proving that that if \(\mathrm{L}=\mathrm{NL}\), then for every \(s\)-state \(\sigma\)-symbol 2NFA there is a \(\mathrm{poly}(s\sigma)\)-state 2DFA which agrees with it on all inputs of length \(\leq s\)'' (see [\textit{P. Berman} and \textit{A. Lingas}, On complexity of regular languages in terms of finite automata. Warsaw: Institute of Computer Science, Polish Academy of Sciences (1977; Zbl 0364.68057)]). In the abstract of the present paper the authors write: ``We recast the question whether \(\mathrm{L}/\mathrm{poly}\supseteq\mathrm{NL}\) in terms of deterministic and nondeterministic two-way finite automata (2DFAs and 2NFAs). We prove it equivalent to the question whether every \(s\)-state unary 2NFA has an equivalent poly\((s)\)-state 2DFA, or whether a poly\((h)\)-state 2DFA can check accessibility in \(h\)-vertex graphs (even under unary encoding) or check two-way liveness in \(h\)-tall, \(h\)-column graphs. This complements two recent improvements of an old theorem of Berman and Lingas. On the way, we introduce new types of reductions between regular languages, use them to prove the completeness of specific languages for two-way nondeterministic polynomial size, and propose a purely combinatorial conjecture that implies \(\mathrm{L}/\mathrm{poly}\not\supseteq\mathrm{NL}\).''