Unprovability of P = NP in PV

Let ff be a polynomial-time algorithm, viewed as a function symbol of PV\mathsf{PV}, and let

φP=NP(f):=xy[ψSAT(x,y)ψSAT(x,f(x))]\varphi_{\mathsf{P} = \mathsf{NP}}(f):= \forall x\,\forall y\,[\psi_{\mathsf{SAT}}(x,y) \rightarrow \psi_{\mathsf{SAT}}(x,f(x))]

where ψSAT(x,y)\psi_{\mathsf{SAT}}(x,y) expresses that yy satisfies the Boolean formula encoded by xx. Unprovability conjecture. For no polynomial-time algorithm ff does theory PV\mathsf{PV} prove the sentence φP=NP(f)\varphi_{\mathsf{P} = \mathsf{NP}}(f). This is a formal weakening of the conjecture that PNP\mathsf{P} \neq \mathsf{NP}: if P=NP\mathsf{P} = \mathsf{NP}, the equality should nevertheless not be provable using only polynomial-time concepts and reasoning. By standard conservation results, the claim is also equivalent to consistency of PV\mathsf{PV} and S21\mathsf{S}^1_2 with PNP\mathsf{P} \neq \mathsf{NP} in the intended sense.

Sources & referencesView supporting material

Primary source

Jan Bydzovsky, Jan Krajicek and Igor C. Oliveira, “Consistency of circuit lower bounds with bounded theories”, arXiv:1905.12935 (2020).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.