Re:A Quasipolynomial Time Algorithm for Graph Isomorphism: T...
by abetusk on Thursday November 12, 2015 @03:29PM
(#10555877)
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/consequence...
Re:A Quasipolynomial Time Algorithm for Graph Isomorphism: T...
by maweki on Thursday November 12, 2015 @03:37PM
(#10555924)
Well, 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.
That is what breaks P=NP for me and I just can't wrap my head around how that would be possible.