Constructibility and the P versus NP problem
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913160553824256 |
|---|---|
| author | Hole, Arne |
| author_facet | Hole, Arne |
| contents | The P versus NP problem is addressed in a context of provability and limitations on the possibility of finding sound axioms for formal theories. It is shown that if the term "constructible theory" is defined in a way which satisfies certain natural conditions, then no constructible, arithmetically sound and formalizable theory proves P = NP. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_16843 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Constructibility and the P versus NP problem Hole, Arne Computational Complexity Logic in Computer Science F.0, F.1.3, F.2.0, F.4.0 F.0; F.1.3; F.2.0; F.4.0 The P versus NP problem is addressed in a context of provability and limitations on the possibility of finding sound axioms for formal theories. It is shown that if the term "constructible theory" is defined in a way which satisfies certain natural conditions, then no constructible, arithmetically sound and formalizable theory proves P = NP. |
| title | Constructibility and the P versus NP problem |
| topic | Computational Complexity Logic in Computer Science F.0, F.1.3, F.2.0, F.4.0 F.0; F.1.3; F.2.0; F.4.0 |
| url | https://arxiv.org/abs/2406.16843 |