Unprovability of P = NP in PV
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.
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.