Resolution of the Linear-Bounded Automata Question

This work resolve a longstanding open question in automata theory, i.e. the {\it linear-bounded automata question} ( shortly, {\it LBA question}), which can also be phrased succinctly in the language of computational complexity theory as $NSPACE[n]\overset{?}{=}DSPACE[n]$. We prove that $NSPACE[n]\neq DSPACE[n]$. Our proof technique is based on diagonalization against all deterministic Turing machines working in $O(n)$ space by an universal nondeterministic Turing machine running in $O(n)$ space. Our proof also implies the following consequences: (1) There exists no deterministic Turing machine working in $O(\log n)$ space deciding the $st$-connectivity question (STCON); (2) $L\neq NL$; (3) $L\neq P$.