The Solver's Paradox in Formal Problem Spaces
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_ | 1866909911350247424 |
|---|---|
| author | Rosko, Milan |
| author_facet | Rosko, Milan |
| contents | This paper investigates how global decision problems over arithmetically represented domains acquire reflective structure through class-quantification. Arithmetization forces diagonal fixed points whose verification requires reflection beyond finitary means, producing Feferman-style obstructions independent of computational technique. We use this mechanism to analyze uniform complexity statements, including $\mathsf{P}$ vs. $\mathsf{NP}$, showing that their difficulty stems from structural impredicativity rather than methodological limitations. The focus is not on deriving separations but on clarifying the logical status of such arithmetized assertions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_14665 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Solver's Paradox in Formal Problem Spaces Rosko, Milan Computational Complexity Logic in Computer Science Logic 68Q15 (Primary), 03F30, 03B40, 68Q05 (Secondary) F.1.3; F.4.1; F.3.1 This paper investigates how global decision problems over arithmetically represented domains acquire reflective structure through class-quantification. Arithmetization forces diagonal fixed points whose verification requires reflection beyond finitary means, producing Feferman-style obstructions independent of computational technique. We use this mechanism to analyze uniform complexity statements, including $\mathsf{P}$ vs. $\mathsf{NP}$, showing that their difficulty stems from structural impredicativity rather than methodological limitations. The focus is not on deriving separations but on clarifying the logical status of such arithmetized assertions. |
| title | The Solver's Paradox in Formal Problem Spaces |
| topic | Computational Complexity Logic in Computer Science Logic 68Q15 (Primary), 03F30, 03B40, 68Q05 (Secondary) F.1.3; F.4.1; F.3.1 |
| url | https://arxiv.org/abs/2511.14665 |