Consequences of an exotic definition for P=NP

摘要

We introduce a formal sentence noted [P=NP]F (the “exotic definition”) that is intuitively equivalent to P=NP; however P=NP and [P=NP]F may not be equivalent in ZFC for some choices of F. Again for some F we show that [P=NP]F is consistent with ZFC, and so is the equivalence [P=NP]F↔[P=NP]. We finally derive a consistency result for P=NP itself.