{wiki}

Complexity: <NP-intermediate> as of 2020:
* expected not to be <NP-complete> because it would imply NP != <Co-NP>: https://cstheory.stackexchange.com/questions/167/what-are-the-consequences-of-factoring-being-np-complete#comment104849_169
* expected not to be in <P (complexity)> because "could we be that dumb that we haven't found a solution after having tried for that long?

The basis of RSA: <RSA (cryptosystem)>. But not proved <NP-complete>, which leads to:


Integer factorization

{c}
{wiki}

* https://math.stackexchange.com/questions/361422/why-isnt-np-conp "Why isn't NP = coNP?"
* https://stackoverflow.com/questions/17046440/whats-the-difference-between-np-and-co-np
* https://cs.stackexchange.com/questions/9795/is-the-open-question-np-co-np-the-same-as-p-np
* https://mathoverflow.net/questions/31821/problems-known-to-be-in-both-np-and-conp-but-not-known-to-be-in-p


Ciro Santilli @cirosantilli 37

 Incoming links: Co-NP