Resolution of The Linear-Bounded Automata Question

Abstract

This paper resolves a famous and longstanding open question in automata theory, i.e., the {\it linear-bounded automata question} (or, for short, the LBA question), which can also be phrased succinctly in the language of computational complexity theory as $$\mathrm{NSPACE}[n]\stackrel{?}{=}\mathrm{DSPACE}[n].$$ In fact, we prove a more general result that $$\mathrm{DSPACE}[S(n)]⫋\mathrm{NSPACE}[S(n)],$$where $S(n)\ge n$ is a space-constructible function. Our proof technique is based on diagonalization against deterministic $S(n)$ space-bounded Turing machines by means of a universal nondeterministic Turing machine, together with other novel and interesting new techniques developed in this paper. Our proof also implies the following consequences, which resolve some famous open questions in complexity theory: (1). $\mathrm{DSPACE}[n]⫋\mathrm{NSPACE}[n]$; (2). $L⫋NL$; (3). $L⫋P$; (4). There exists no deterministic Turing machine working in $O(\log n)$ space that decides the $st$-connectivity question (STCON).

[v23] Full-text language polished; full-text grammatical mistakes corrected; we wish you will enjoy the proofs in this work