A proof of P!=NP
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2020
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915792976609280 |
|---|---|
| author | McCallum, Rupert |
| author_facet | McCallum, Rupert |
| contents | 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 SEFA. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2005_10080 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | A proof of P!=NP McCallum, Rupert Logic Computational Complexity 03D15 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 SEFA. |
| title | A proof of P!=NP |
| topic | Logic Computational Complexity 03D15 |
| url | https://arxiv.org/abs/2005.10080 |