论文标题
P！= NP的证明
A proof of P!=NP
论文作者
论文摘要
我们在PA中证明，有一个算术上可以定义的序列$ \ {ϕ_ {n}：n \ inω\} $ of $π^{0} _ {2} $句子，使得 -pra+$ \ {ϕ_ {n}：n \ inω\} $ is $π^{0} _ {2} $ - 声音和$π^{0} _ {1} $ - 完成 - $ ϕ_ {n} $的长度在上面由$ n $的多项式函数限制，并带有正系数 -pra+$ ϕ_ {n+1} $总是证明PRA+$ ϕ_ {n} $的1个一致性。 人们认为，逻辑强度的增长在某种意义上是“尽可能快的”，这表明了以下事实：序列中的真实$π^{0} _ {0} _ {2} $句子所主张的总体递归函数在所有总体递归功能的集合中都是齐弗纳尔生长利率。然后，我们开发了一个论点，该论点利用了一系列句子，该句子是通过对角线引理的应用构建的，这是Hugh Woodin在他的文章《河内塔》第18章中概述的Hugh Woodin的“河内塔”结构的广泛概括。该论点确定结果可以证明它可以证明$ p \ neq np $。我们指出了如何将论点一直降低到EFA。
We show that it is provable in PA that there is an arithmetically definable sequence $\{ϕ_{n}:n \in ω\}$ of $Π^{0}_{2}$-sentences, such that - PRA+$\{ϕ_{n}:n \in ω\}$ is $Π^{0}_{2}$-sound and $Π^{0}_{1}$-complete - the length of $ϕ_{n}$ is bounded above by a polynomial function of $n$ with positive leading coefficient - PRA+$ϕ_{n+1}$ always proves 1-consistency of PRA+$ϕ_{n}$. One has that the growth in logical strength is in some sense "as fast as possible", manifested in the fact that the total general recursive functions whose totality is asserted by the true $Π^{0}_{2}$-sentences in the sequence are cofinal growth-rate-wise in the set of all total general recursive functions. We then develop an argument which makes use of a sequence of sentences constructed by an application of the diagonal lemma, which are generalisations in a broad sense of Hugh Woodin's "Tower of Hanoi" construction as outlined in his essay "Tower of Hanoi" in Chapter 18 of the anthology "Truth in Mathematics". The argument establishes the result that it is provable in PA that $P \neq NP$. We indicate how to pull the argument all the way down into EFA.
