1 – If ZFC is consistent, ZFC proofs are NP-complete.
2 – If ZFC proofs are NP-complete, then: ZFC is inconsistent –> P = NP.
3 – If ZFC proofs are NP-complete, then: P != NP –> ZFC is consistent.
4 – If ZFC is consistent, then P != NP cannot be proved in ZFC.
1) If ZFC is consistent, then there exist both theorems and non-theorems of ZFC. Based on any given SAT instance, we can construct a proposition that is an existentially quantified boolean proposition, where each variable is itself intended to be a proposition. For example: “there exists x1 s.t. there exists x2 s.t. there exists x3 s.t. (x1 ^ x2 ^ !x3) v (x3 ^ !x2) v (!x1 ^ !x1 ^ x3 ^ !x2 ^ x1)”. For each variable x1, x2, … , x_n, let x_i be one of two propositions from ZFC: provable_prop or !provable_prop (i.e., the negation of provable_prop).
If the initial SAT instance that we are mapping to a ZFC proposition is satisfiable, then we need only select x1, x2, … , x_n so that each x_i is either provable_prop or !provable_prop and the proposition is satisfied. Once we’ve done this, we’ll find that the resulting proposition simplifies to provable_prop, which is itself a theorem, implying that there do indeed exist propositions x1, x2, … , x_n s.t. the main proposition is a theorem.
On the other hand, if the initial SAT instance is unsatisfiable, then the main ZFC proposition that we map to will have no possible assignments to the literals (x1, x2, … , x_n) that will yield a provable proposition. This is clear because the ZFC proposition simplifies to a contradiction, which cannot be proved if ZFC is consistent.
So, considering the decision problem PROOF, which is to decide if, given a ZFC proposition and a string of all 1′s, there exists a proof of the proposition of length <= the length of the string of 1′s, we can now show that:
We wish to show: If ZFC is consistent, PROOF is NP-complete.
We showed a reduction from SAT to PROOF above that is contingent on the consistency of ZFC; further, PROOF is clearly NP, since proofs are checkable in polynomial time and the length of the proof to be guessed is linear in the size of the string of 1′s. Thus PROOF is NP-complete.
2) Assume ZFC proofs (that is, proving a theorem given the proof’s length in unary) are NP-complete. Then assume ZFC is inconsistent. Then we have that we can find a contradiction in ZFC in constant space and time. Further, every proposition in ZFC can be proved, and a proof can be found in polynomial time. So since ZFC proofs are NP-complete and also polynomial time, we have that P = NP. (If not enough space is available to generate the full proof of the contradiction in ZFC, we can still guess all possible proofs of the theorem in constant time and see if one of them works, since the proof allocated for the theorem must be shorter than the proof of the contradiction.)
3) This follows from the contraposition of the above (#2).
4) Assume ZFC is consistent. Then we have that “ZFC proofs are NP-complete,” (see step one), and that “ZFC proofs are NP-complete –> (P != NP –> ZFC is consistent).” Thus we get that our assumption implies “P != NP –> ZFC is consistent.” So: ”ZFC is consistent –> (P != NP –> ZFC is consistent).”
Now let’s examine the statement “P != NP –> ZFC is consistent” by itself. By Godel’s second incompleteness theorem, we have that ZFC is consistent cannot be proved within ZFC unless ZFC is inconsistent. So if we had a proof that P != NP (in ZFC), then we would have a proof that ZFC is consistent, implying that ZFC is not consistent. Thus, we can conclude that “(P != NP –> ZFC is consistent) –> (ZFC is consistent –> P != NP cannot be proved in ZFC).”
Above, we saw that “ZFC is consistent –> (P != NP –> ZFC is consistent).” Just now, we saw that “(P != NP –> ZFC is consistent) –> (ZFC is consistent –> P != NP cannot be proved in ZFC).” From these two statements, we can conclude: ”ZFC is consistent –> (ZFC is consistent –> P != NP cannot be proved in ZFC).” This simplifies to: ”ZFC is consistent –> P != NP cannot be proved in ZFC.”