On the consistency of $P=NP$ with fragments of ZFC whose own consistency strength can be measured by an ordinal assignment
| dc.creator | da Costa, N. C. A. | |
| dc.creator | Doria, F. A. | |
| dc.date | 2000-06-10 | |
| dc.date.accessioned | 2026-07-07T04:35:50Z | |
| dc.date.available | 2026-07-07T04:35:50Z | |
| dc.description | We formulate the $P<NP$ hypothesis in the case of the satisfiability problem as a $Π^0_2$ sentence, out of which we can construct a partial recursive function $f_{\neg A}$ so that $f_{\neg A}$ is total if and only if $P < NP$. We then show that if $f_{\neg 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}$. | |
| dc.description | LaTeX, 19 pages, no figures | |
| dc.identifier | https://arxiv.org/abs/math/0006079 | |
| dc.identifier | http://arxiv.org/abs/math/0006079 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/59391 | |
| dc.subject | Logic | |
| dc.title | On the consistency of $P=NP$ with fragments of ZFC whose own consistency strength can be measured by an ordinal assignment | |
| dc.type | text |