In a given public key cryptosystem, if the problem of determining the private key from the public key is NP-complete or co-NP-complete, does that imply that NP = co-NP?

Complexity theory is definitely not my specialty. I ask because from what I read that it seems that this would be the case (informally):

Determining the private key from the public key can be converted to a decision problem by asking whether a given bit of the private key is $1$. The complement of this problem is then asking whether a given bit is not $1$ (that is, $0$). For both problems, the entire private key is a certificate. Clearly they are polynomial-time reducible to each other.

If either decision problem were NP-complete or co-NP-complete, wouldn't that imply NP = co-NP?

  • $\begingroup$ The title and body don't match. Also, you mean and instead of or? There is an answer in CS for this intersection, and this question might be asked there, too. $\endgroup$ – kelalaka Jan 31 at 22:32
  • $\begingroup$ @kelalaka Fixed the title; thanks. I think that one would imply the other, so using "or" versus "and" would be the same thing? $\endgroup$ – Myria Jan 31 at 22:47
  • $\begingroup$ Or only false if both are false. So this has three sub-questions; the problem of determining the private key from the public key (1) is NP-complete, (2) is co-NP-complete (3) NP-complete and co-NP-complete. $\endgroup$ – kelalaka Jan 31 at 22:53
  • $\begingroup$ @kelalaka If either one is NP-complete or co-NP-complete, that they are their own complement (within polynomial-time reduction) would imply NP = co-NP, right? $\endgroup$ – Myria Jan 31 at 22:57

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.