Are there any major implications of NP = coNP (if true) the way there would be if P=NP? I'm thinking of real-world implications analogous to the encryption-pocalypse (excuse the drama) that would happen if P=NP.
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
This got a bit too long for a comment, I might edit this to provide a more coherent answer at a later point. There is this answer to Is it possible to construct an encryption scheme for which breaking is NP complete but there nearly always exists an efficient breaking algorithm on crypto stackexchange. It argues, we want hard problems for encryption to be in both NP and coNP. So I would say we might have some hope for designing actually good cryptosystems from NP-complete problems instead of having to design them from problems in that intersection. See here for what we know about possibility of complete problems for the intersection.
