Refuting Tianrong Lin's arXiv:2110.05942 "Resolution of The Linear-Bounded Automata Question"

Abstract

In the preprint mentioned in the title Mr. Tianrong claims to prove $\text{NSPACE}[n]\ne \text{DSPACE}[n]$, resolving a longstanding open problem in automata theory called the LBA question. He claims to achieve this by showing more generally $\text{NSPACE}[S(n)]\ne \text{DSPACE}[S(n)]$ for suitable $S(n)$. We demonstrate that his proof is incomplete, even wrong, and his strategy cannot be repaired. Update to include recent developments of Mr. Tianrong's preprint.

7 pages, refers to arXiv:2110.05942 by Tianrong Lin