Tagged

A problem that is both NP and NP-hard.
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.
A problem such that all NP problems can be reduced in polynomial time to it.
This is the most interesting class of problems for BQP as we haven't proven that they are neither:
Heck, we know nothing about this class yet related to non quantum classes!

Articles by others on the same topic (0)

There are currently no matching articles.