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.
翻译：Cantor发明了二进制技术,以表明实际数字比代数要多,在计算机科学中非常重要。在这项工作中,我们用一个通用的非确定性图灵机器来计算所有多米时定型图灵机,并对所有图灵机进行分解。结果,我们得到了一种语言,即没有被任何多米时定型图灵机器所接受的L_d$,但被一个非确定性图灵机器所接受,在任何美元(n ⁇ k)范围内,任何美元(k\in\mathbb{N ⁇ 1美元,即$_d\nNP$)以内工作。也就是说,我们提出的一个证据是,美元和美元($P$)不同。
相关内容
微信扫码咨询专知VIP会员