The { \em diagonalization technique} was invented by Georg Cantor to show that there are more real numbers than algebraic numbers and is very crucial in { \em theoretical computer science}. In this work, we enumerate all of the polynomial-time deterministic Turing machines and diagonalize against all of them by a universal nondeterministic Turing machine. As a result, we obtain that there is a language $L_d$ not accepted by any polynomial-time deterministic Turing machines but accepted by a nondeterministic Turing machine running within time $O(n^k)$ for any $k\in\mathbb{ N}_1$. Based on these, we further show that $L_d\in\mathcal{ NP}$. That is, in this work, we present a proof that $\mathcal{ P}$ and $\mathcal{ NP}$ differ. Meanwhile, we show that there exists a language $L_s$ in $\mathcal{ P}$, but the machine accepting it also runs within time $O(n^k)$ for all $k\in\mathbb{ N}_1$. Lastly, we show that if $\mathcal{ P}^O=\mathcal{ NP}^O$ and on some rational base assumptions, then the set $P^O$ of all polynomial-time deterministic oracle Turing machines with oracle $O$ is not enumerable, thus demonstrating that the diagonalization technique ({ \em via a universal nondeterministic oracle Turing machine}) will generally { \em not} apply to the relativized versions of the $\mathcal{ P}$ versus $\mathcal{ NP}$ problem.
Categories: cs.CC cs.FL