3 ms·
This would mean that NP=Co-NP and that there is a polynomial certificate for every Co-NP problem. That is what breaks P=NP for me and I just can't wrap my head
by maweki 11y ago
This would mean that NP=Co-NP and that there is a polynomial certificate for every Co-NP problem.
That is what breaks P=NP for me and I just can't wrap my head around how that would be possible.
- abetusk 11y agoYour 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.