Diagonalization of Polynomial-Time Deterministic Turing Machines Via Nondeterministic Turing Machine

The diagonalization technique was invented by Georg 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 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 working within $O(n^k)$ for any $k\in\mathbb{N}_1$. By this, we further show that $L_d\in \mathcal{NP}$ . That is, we present a proof that $\mathcal{P}$ and $\mathcal{NP}$ differ.Comment: (v12/3/4/5/6): The review report from "Annals of Mathematics" attached. As of today, no experts deny that $L_d\in\mathcal{NP}$ from the report; typos corrected. Additional open question added. [v16] JACM's area editor completely unable to present counterexamples from the report (But surprising, the referee's comments being masked by area editor