5

No one knows, but: It is suspected that neither factoring nor discrete logarithm are NP-complete, but we have no proof. (Evidence for the suspicion: they are in NP $\cap$ coNP. See, e.g., https://cstheory.stackexchange.com/q/159/5038, https://cstheory.stackexchange.com/q/167/5038 for factoring. It's similarly easy to prove that discrete log is in NP $\...


1

In short yes Proof Let's assume $X$ is NP-complete and $X$ is in co-NP. We show that $NP \subseteq coNP$ and viceversa. [$NP\subseteq coNP$] Because $X$ is NP-complete $=>$ for each $L\in NP$ we can found a polytime function $f$ that $s\in L$ iff $f(s)\in X$. But $X$ is in coNP $=>$ for the polityme reduction closure of coNP, $L\in coNP$ too $=&...


Only top voted, non community-wiki answers of a minimum length are eligible