Cheap and Secure Web Hosting Provider : See Now

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

, , No Comments
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?

Asked By : asdf

Answered By : D.W.

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.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback