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}), which can also be phrased succinctly in the language of computational complexity theory as $DSPACE[n]\overset{?}{=} NSPACE[n]$. We show first that $DSPACE[n]\neq NSPACE[n]$. Then, we show by padding argument that $DSPACE[\log n]\neq NSPACE[\log n]$. Our proof technique is primarily based on diagonalization by a universal nondeterministic $n$ space-bounded Turing machine against all deterministic $n$ space-bounded Turing machines. Our proof also implies the following fundamental consequences: (1) There is no deterministic Turing machine of space complexity $\log n$ deciding the $st$-connectivity question (STCON); (2) $L\neq P$.