Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2404.00468 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917627001044992 |
|---|---|
| author | Williamson, S Gill |
| author_facet | Williamson, S Gill |
| contents | Our main result, Theorem 3.3, uses Friedman's Jump Free Theorem, Theorem 2.7, which he has shown to be independent of ZFC, the usual axioms of set theory. We conjecture that Theorem 3.3, a straight forward translation of the statement of Theorem 2.7 into sets and functions, is also independent of ZFC as is its immediate Corollary 3.4. It is easy to show that a proof that P=NP will also prove Corollary 3.4. If Corollary 3.4 is in fact independent of ZFC then a ZFC proof of P=NP is impossible, perhaps because it is false. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_00468 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On P=NP Either False or Independent of ZFC Williamson, S Gill Logic Combinatorics 0368 Our main result, Theorem 3.3, uses Friedman's Jump Free Theorem, Theorem 2.7, which he has shown to be independent of ZFC, the usual axioms of set theory. We conjecture that Theorem 3.3, a straight forward translation of the statement of Theorem 2.7 into sets and functions, is also independent of ZFC as is its immediate Corollary 3.4. It is easy to show that a proof that P=NP will also prove Corollary 3.4. If Corollary 3.4 is in fact independent of ZFC then a ZFC proof of P=NP is impossible, perhaps because it is false. |
| title | On P=NP Either False or Independent of ZFC |
| topic | Logic Combinatorics 0368 |
| url | https://arxiv.org/abs/2404.00468 |