AGI-complete Updated +Created
Term invented by Ciro Santilli to refer to problems that can only be solved once we have AGI.
It is somewhat of a flawed analogy to NP-complete.
BQP Updated +Created
Heck, we know nothing about this class yet related to non quantum classes!
Integer factorization Updated +Created
Complexity: NP-intermediate as of 2020:
The basis of RSA: RSA. But not proved NP-complete, which leads to:
NP-intermediate Updated +Created
This is the most interesting class of problems for BQP as we haven't proven that they are neither:
P versus NP problem Updated +Created
Interesting because of the Cook-Levin theorem: if only a single NP-complete problem were in P, then all NP-complete problems would also be P!
We all know the answer for this: either false or independent.