On Formally Undecidable Propositions of Nondeterministic Complexity and Related Classes
This is a foundational critique of computational complexity theory, potentially challenging the definition of NP and related classes.
The paper argues that the standard definition of NP is unsatisfiable because it implicitly asserts a property that Gödel's First Incompleteness Theorem prohibits, showing that NP contains languages where truth and bounded provability coincide in a way that leads to contradictions.
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.