论文标题
在P与NP上
On P Versus NP
论文作者
论文摘要
结果表明，任何确定性TM都无法在多项式时间内解决图理论问题集团。这升级了众所周知的部分结果，该结果仅声称单调性能不可分性，并最终暗示了p $ \ neq $ np，因为Clique是NP完整的。本文实质上简化了我以前的演示文稿，该介绍使用了基于标准布尔语义的更复杂的计算模型，同时修复了RenéThiemann已实施的通用证明助手Isabelle发现的技术错误。
It is shown that graph-theoretic problem CLIQUE can't be solved in polynomial time by any deterministic TM. This upgrades the well-known partial result that claims only monotone unsolvability thereof, and eventually implies P $\neq$ NP as CLIQUE is NP-complete. This paper essentially simplifies my previous presentation that used more complex models of computation based on standard Boolean semantics while fixing technical errors spotted by a generic proof assistant Isabelle that has been implemented by René Thiemann.
