Meta-Mathematics of Computational Complexity Theory
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910905106694144 |
|---|---|
| author | Oliveira, Igor C. |
| author_facet | Oliveira, Igor C. |
| contents | We survey results on the formalization and independence of mathematical statements related to major open problems in computational complexity theory. Our primary focus is on recent findings concerning the (un)provability of complexity bounds within theories of bounded arithmetic. This includes the techniques employed and related open problems, such as the (non)existence of a feasible proof that P = NP. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_04416 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Meta-Mathematics of Computational Complexity Theory Oliveira, Igor C. Computational Complexity Logic in Computer Science Logic We survey results on the formalization and independence of mathematical statements related to major open problems in computational complexity theory. Our primary focus is on recent findings concerning the (un)provability of complexity bounds within theories of bounded arithmetic. This includes the techniques employed and related open problems, such as the (non)existence of a feasible proof that P = NP. |
| title | Meta-Mathematics of Computational Complexity Theory |
| topic | Computational Complexity Logic in Computer Science Logic |
| url | https://arxiv.org/abs/2504.04416 |