The most famous open problem in Computer science is whether P = NP or not, but a less famous yet related problem is whether NP = Co-NP, now what kind of chaos could this cause if it was true? I actually am having a hard time comprehending how it would look.
As I understand, a proof to (for example) P = NP, would be that we found a method to solve an NP complete problem in polynomial time, but when it comes to the other problem, what are we waiting for/expecting? that a problem is equal to its complement? how could it be that? I am not looking for a proof, just an intuitive understanding/explanation of what this actually means.
What I read and understood is for example, 3SAT is an NP complete problem, and its complement would be whether a DNF function is a Tautology or not, which is in Co-NP Complete, now are we looking for some sort of reduction for example from one to the other in polynomial time, i.e. transforming/turning one into the other "quickly"? or am I on the wrong track?
Thank you,
The main consequence would be the collapse of the polynomial hierarchy above NP. Indeed $\mathbf{NP} = co{-}\mathbf{NP}$ implies $\mathbf{NP} = \mathbf{PH}$.