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

N. C. A. da Costa, F. A. Doria

We formulate the $P<NP$ hypothesis in the case of the satisfiability problem as a ${\Pi }_2^0$ sentence, out of which we can construct a partial recursive function $f_{\neg A}$ so that…