Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2604.07406 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915924202749952 |
|---|---|
| author | Kolář, Martin |
| author_facet | Kolář, Martin |
| contents | The definition of \NP\ requires, for each member language~$L$, a polynomial-time checking relation~$R$ and a constant~$k$ such that $w \in L \iff \exists y\,(|y| \leq |w|^k \wedge R(w,y))$. We show that this biconditional instantiates, for each member language, Hilbert's triple: a sound, complete, decidable proof system in which truth-in-$L$ and bounded provability coincide by fiat. We show further that the polynomial-time restriction on~$R$ does not exclude Gödel's proof-checking relation, which is itself polynomial-time and fits the definition as a literal instance. Hence \NP, taken as a totality over all polynomial-time~$R$, contains languages for which the biconditional asserts a property that Gödel's First Incompleteness Theorem prohibits. The semantic definition of \NP\ is unsatisfiable, for the same reason that Hilbert's Program is. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_07406 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On Formally Undecidable Propositions of Nondeterministic Complexity and Related Classes Kolář, Martin Computational Complexity The definition of \NP\ requires, for each member language~$L$, a polynomial-time checking relation~$R$ and a constant~$k$ such that $w \in L \iff \exists y\,(|y| \leq |w|^k \wedge R(w,y))$. We show that this biconditional instantiates, for each member language, Hilbert's triple: a sound, complete, decidable proof system in which truth-in-$L$ and bounded provability coincide by fiat. We show further that the polynomial-time restriction on~$R$ does not exclude Gödel's proof-checking relation, which is itself polynomial-time and fits the definition as a literal instance. Hence \NP, taken as a totality over all polynomial-time~$R$, contains languages for which the biconditional asserts a property that Gödel's First Incompleteness Theorem prohibits. The semantic definition of \NP\ is unsatisfiable, for the same reason that Hilbert's Program is. |
| title | On Formally Undecidable Propositions of Nondeterministic Complexity and Related Classes |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2604.07406 |