New answers tagged


A propositional proof system in which all tautologies have a "short" proof is called a super-propositional-proof system. Such a system exists iff NP = CoNP. If NP != CoNP then P != NP. So, it's not necessarily the only way to prove P != NP, but you could do so by proving a super-propositional-proof system cannot exist.


I believe everything you said is correct. I note that your point #3 could hold regardless of points #1 and #2 - points #1 and #2 are just a concrete example of where this has provably happened.

Top 50 recent answers are included