2021/10/12 by Tianrong Lin, Lin, Tianrong
Computer Science · #68Q15 #68Q17 #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Quantum Computing Algorithms and Architecture
paper · pdf · doi:10.48550/arxiv.2110.06211
openalex publication_date 2021/10/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 Ld not accepted by any polynomial-time deterministic Turing machines but accepted by a nondeterministic Turing machine running within time O(nk) for any k∈ℕ1. Based on these, we further show that Ld\inNP. That is, in this work, we present a proof that P and NP differ. Meanwhile, we show that there exists a language Ls in P, but the machine accepting it also runs within time O(nk) for all k∈ℕ1. Lastly, we show that if PO=NPO and on some rational base assumptions, then the set PO 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 P versus NP problem.