Does Resolving PvNP Require a Paradigm Shift? Part I: A Perspective.
Bhupinder Singh Anand · FCS · 2010
I shall argue that a resolution of the PvNP problem requires building an iff bridge between the domain of provability and that of computability. The former concerns how human minds decide the truth of number-theoretic relations, and is formalised by first-order Peano Arithmetic following Dededekind’s axiomatisation of Peano’s Postulates. The latter concerns how human minds compute the values of number-theoretic functions, and is formalised by the operations of a Turing Machine, following Turing’s analysis of computable functions. I shall show that such a bridge requires objective definitions of both an ‘algorithmic’ interpretation of PA, and an ‘instantiational’ interpretation of PA. I shall show that both interpretations are implicit in the definition of the ‘standard’ interpretation of PA. However the existence of, and distinction between, the two objectively definable interpretations—and the fact that the former is sound whilst the latter is not—is obscured by the extraneous presumption under the ‘standard’ interpretation of PA that Aristotle’s particularisation must hold over the structure N of the natural numbers. I shall argue that recognising the falseness of this belief awaits a paradigm shift in our perception of the application of Tarski’s analysis—of the concept of truth in the languages of the deductive sciences—to the ‘standard’ interpretation of PA. I shall then show that an arithmetical formula [F ] is PA-provable if, and only if, [F ] interprets under a sound interpretation of first order Peano Arithmetic PA as a Boolean arithmetical function F ∗ that is algorithmically computable as tautologically true over N . I shall finally show how it then follows from Godel’s construction of a formally ‘undecidable’ arithmetical proposition that there is a Halting-type tautology which is algorithmically verifiable as a tautolgy, but not algorithmically computable as a