1
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.