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

arXivmath/0006079MaRDI QIDQ6470461FDOQ6470461

Authors: N. C. A. da Costa, Francisco Antonio Doria 

Publication date: 10 June 2000

Abstract: We formulate the $P<NP$ hypothesis in the case of the satisfiability problem as a $P{i}_2^0$ sentence, out of which we can construct a partial recursive function $f_{egA}$ so that $f_{egA}$ is total if and only if $P<NP$. We then show that if $f_{egA}$ is total, then it isn't $calT$--provably total (where $calT$ 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 $calT$.

This page was built for publication: On the consistency of $P=NP$ with fragments of ZFC whose own consistency strength can be measured by an ordinal assignment

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6470461)