# Tag Info

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$=&...