New answers tagged np
1
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.
2
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
