Diagonalization $of$ Polynomial-Time Turing Machines Via Nondeterministic Turing Machine
Tianrong Lin · arXiv (Cornell University) · 2021
The diagonalization technique was invented by Cantor to show that there are more real numbers than algebraic numbers, and is very important in computer science. In this work, we enumerate all polynomial-time deterministic Turing machines and diagonalize over all of them by an 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 working within $O(n^k)$ for any $k\in\mathbb{N}_1$, i.e. $L_d\in NP$ . That is, we present a proof that $P$ and $NP$ differs.