Resolution of the Linear-Bounded Automata Question

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