On the consistency of P=NP with fragments of ZFC whose own consistency strength can be measured by an ordinal assignment

2000/06/10 by N. C. A. da Costa, da Costa, N. C. A., F. A. Doria +1
Mathematics · #FOS: Mathematics #Logic (math.LO) #math.LO

paper · pdf · doi:10.48550/arxiv.math/0006079

LaTeX, 19 pages, no figures

arxiv created 2000/06/10 · arxiv updated 2009/11/30

Abstract

We formulate the P<NP hypothesis in the case of the satisfiability problem as a Π⁰₂ sentence, out of which we can construct a partial recursive function f_{¬ A} so that f_{¬ A} is total if and only if P < NP. We then show that if f_{¬ A} is total, then it isn't \cal T--provably total (where \cal T is a fragment of ZFC that adequately extends PA and whose consistency is of ordinal order). Follows that the negation of P < NP, that is, P = NP, is consistent with those \cal T.

Related

• On P=NP Either False or Independent of ZFC
• A note on an alleged proof of the relative consistency of P=NP with PA
• On the difficulty of proving P equals NP in ZFC
• A proof of P!=NP
• Classifying the provably total set functions of KP and KP(P)