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$.
翻译:这项工作解决了自动化理论中的一个长期未决问题,即用于空间构造功能的美元(n)\ geq\log n$美元,从中可以紧接着DSPACE[n]$\neq$NSPACE[n]\ $NSPACE[$]。我们证明,DSPACE$[(n)]\neq$ NSPACE$[S(n)]\neq$ NSPACE$[S(n)]。我们的证据还表明以下基本后果:(1)没有确定性的空间复杂度的机器(美元);(3)美元(美元);(3)(美元)确定空间复杂度的美元;(3)(美元)美元)问题;(3)(美元)问题;(美元)问题;(3)(美元)问题。