The Separation of $NP$ and $PSPACE$

There is an important and interesting open question in computational complexity on the relation between the complexity classes $\mathcal{N}\mathcal{P}$ and $\mathcal{P}\mathcal{S}\mathcal{P}\mathcal{A}\mathcal{C}\mathcal{E}$. It is a widespread belief that $\mathcal{N}\mathcal{P}\mathrm{\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{N}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}[S(n)]\subseteq \mathrm{D}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}[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{N}\mathcal{P}⫋\mathcal{P}\mathcal{S}\mathcal{P}\mathcal{A}\mathcal{C}\mathcal{E}\mathrm{.}$$ 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.