# If finding a private key from a public key is [co-]NP-complete, does NP=co-NP?

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?

• 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. – kelalaka Jan 31 '19 at 22:32
• @kelalaka Fixed the title; thanks. I think that one would imply the other, so using "or" versus "and" would be the same thing? – Myria Jan 31 '19 at 22:47
• 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. – kelalaka Jan 31 '19 at 22:53
• @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? – Myria Jan 31 '19 at 22:57