Resolution of The Linear-Bounded Automata Question
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909621388574720 |
|---|---|
| author | Lin, Tianrong |
| author_facet | Lin, Tianrong |
| contents | This paper resolves a famous and longstanding open question in automata theory, i.e., the {\it linear-bounded automata question} (or shortly, LBA question), which can also be phrased succinctly in the language of computational complexity theory as $$ {\rm NSPACE}[n]\overset{?}{=}{\rm DSPACE}[n]. $$ In fact, we prove a more general result that $$ {\rm DSPACE}[S(n)]\subsetneqq {\rm NSPACE}[S(n)] $$ where $S(n)\geq n$ is a space-constructible function. Our proof technique is based on diagonalization against deterministic $S(n)$ space-bounded Turing machines with a universal nondeterministic Turing machine and on other novel and interesting new techniques. Our proof also implies the following consequences, which resolve some famous open questions in complexity theory:
(1). ${\rm DSPACE}[n]\subsetneqq {\rm NSPACE}[n]$;
(2). $L\subsetneqq NL$;
(3). $L\subsetneqq P$;
(4). There exists no deterministic Turing machine working in $O(\log n)$ space deciding the $st$-connectivity question (STCON). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2110_05942 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Resolution of The Linear-Bounded Automata Question Lin, Tianrong Computational Complexity Formal Languages and Automata Theory 68Q15, 68Q17 This paper resolves a famous and longstanding open question in automata theory, i.e., the {\it linear-bounded automata question} (or shortly, LBA question), which can also be phrased succinctly in the language of computational complexity theory as $$ {\rm NSPACE}[n]\overset{?}{=}{\rm DSPACE}[n]. $$ In fact, we prove a more general result that $$ {\rm DSPACE}[S(n)]\subsetneqq {\rm NSPACE}[S(n)] $$ where $S(n)\geq n$ is a space-constructible function. Our proof technique is based on diagonalization against deterministic $S(n)$ space-bounded Turing machines with a universal nondeterministic Turing machine and on other novel and interesting new techniques. Our proof also implies the following consequences, which resolve some famous open questions in complexity theory: (1). ${\rm DSPACE}[n]\subsetneqq {\rm NSPACE}[n]$; (2). $L\subsetneqq NL$; (3). $L\subsetneqq P$; (4). There exists no deterministic Turing machine working in $O(\log n)$ space deciding the $st$-connectivity question (STCON). |
| title | Resolution of The Linear-Bounded Automata Question |
| topic | Computational Complexity Formal Languages and Automata Theory 68Q15, 68Q17 |
| url | https://arxiv.org/abs/2110.05942 |