The Separation of $NP$ and $PSPACE$

Abstract

There is an important and interesting open question in computational complexity on the relation between the complexity classes $\mathcal{NP}$ and $\mathcal{P}\mathcal{S}\mathcal{P}\mathcal{A}\mathcal{C}\mathcal{E}$. It is a widespread belief that $\mathcal{NP}\ne \mathcal{P}\mathcal{S}\mathcal{P}\mathcal{A}\mathcal{C}\mathcal{E}$. In this paper, we confirm this conjecture affirmatively by showing that there is a language $L_d$ accepted by no polynomial-time nondeterministic Turing machines but accepted by a nondeterministic Turing machine running within space $O(n^k)$ for all $k\in {\mathbb{N}}_1$. We achieve this by virtue of the prerequisite of $$\mathrm{NTIME}[S(n)]\subseteq \mathrm{DSPACE}S(n)],$$ and then by diagonalization against all polynomial-time nondeterministic Turing machines via a universal nondeterministic Turing machine $M_0$. We further show that $L_d\in \mathcal{P}\mathcal{S}\mathcal{P}\mathcal{A}\mathcal{C}\mathcal{E}$, which leads to the conclusion $$\mathcal{NP}⫋\mathcal{P}\mathcal{S}\mathcal{P}\mathcal{A}\mathcal{C}\mathcal{E}.$$ Our approach is based on standard diagonalization and novel new techniques developed in the author's recent works \cite{Lin21a,Lin21b} with some new refinement.

[v24] revised for clarity; 21 pages, 1 figure; we wish you will enjoy the proofs; arXiv admin note: text overlap with arXiv:2110.06211