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?