Cheap and Secure Web Hosting Provider : See Now

# [Answers] Is Simon's problem a good NP-intermediate candidate?

, ,
Problem Detail:

We know that \$BPP \subseteq BQP\$ but we have no proof \$BPP \subset BQP\$ (Though we have the proof that BQP \$!=\$ BPP with an oracle)

Since Simon's problem (as factoring) it's easily solvable by a quantum computer, and in exponential time complexity solvable by a classical computer, that's a hint of the separation between BQP and BPP and therefore this can be a pure NP problem. Am I right?

Simon's problem is not a pure NP problem, for two reasons:

• It is an oracle problem. We are given an oracle for some function \$f\$. That's not something that you can do within the definition of a NP problem.

• It is a promise problem. We are given the promise that \$f\$ will satisfy a particular property (it is two-to-one, and has a particular structure). That too is not something you can do within the definition of a NP problem.

So Simon's problem is not a problem in the formal complexity class NP; it's just something different. For the same reasons, it's not NP-intermediate, either.