4 ms·
Your comment is a little hard to parse. We could live in a world where there are short proofs that an NP-Complete problem is unsolvable but those short proofs
by abetusk 11y ago
Your comment is a little hard to parse. We could live in a world where there are short proofs that an NP-Complete problem is unsolvable but those short proofs are hard to find (i.e. NP=co-NP but P!=NP) [1]. I think there are other consequences but that's an area I don't know that much about.
[1] http://cstheory.stackexchange.com/questions/8087/consequences-of-np-conp-and-p-ne-np http://cstheory.stackexchange.com/questions/8087/consequence...
- maweki 11y agoWell, you've read my implication-arrow the wrong way. Since I don't believe that NP=co-NP (in any case), I can't believe that P=NP because Co-P=P. So if the collapse would happen (what the OP mentioned as a possibility), one implication would be NP=co-NP. I don't believe that so I can't believe in collapse.