Unprovability of P = NP in PV
Let be a polynomial-time algorithm, viewed as a function symbol of , and let
where expresses that satisfies the Boolean formula encoded by . Unprovability conjecture. For no polynomial-time algorithm does theory prove the sentence . This is a formal weakening of the conjecture that : if , 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 and with in the intended sense.
References
Primary source
Jan Bydzovsky, Jan Krajicek and Igor C. Oliveira, “Consistency of circuit lower bounds with bounded theories”, arXiv:1905.12935 (2020).
Progress summary
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.