Resolution of the Linear-Bounded Automata Question

This work resolves a longstanding open question in automata theory, i.e., the {\it linear-bounded automata question} ({\it 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$[n]\neq$ NSPACE$[S(n)]$. Our proof technique is mainly based on diagonalization against all deterministic Turing machines of space complexity $S(n)=n$ by an universal nondeterministic Turing machine of space complexity $S(n)=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$.