On Formally Undecidable Propositions of Nondeterministic Complexity and Related Classes

arXiv:2604.07406v1 Announce Type: new
Abstract: 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”odel’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”odel’s First Incompleteness Theorem prohibits. The semantic definition of NP is unsatisfiable, for the same reason that Hilbert’s Program is.