Click here to flash read.
The diagonalization technique was invented by Georg Cantor to show that there
are more real numbers than algebraic numbers and is very important in {\em
theoretical 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 time
$O(n^k)$ for all $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.
Click here to read this post out
ID: 33602; Unique Viewers: 0
Unique Voters: 0
Total Votes: 0
Votes:
Latest Change: April 1, 2023, 7:34 a.m.
Changes:
Dictionaries:
Words:
Spaces:
Views: 8
CC:
No creative common's license
No creative common's license
Comments: