Does Resolving PvNP Require a Paradigm Shift? Part III: Consequences of a Sound, Algorithmic Interpretation of PA.
Bhupinder Singh Anand · FCS · 2010
I show that an arithmetical formula [F ] is PAprovable if, and only if, it interprets as an arithmetical expression F ∗—under a sound interpretation of PA—such that F ∗ is algorithmically decidable as true over the structure N of the natural numbers. I show how this implies, first, that P 6=NP and, second, that Church’s thesis is false.