I have taken one basic class in complexity and understand the fundamentals. E.g. P, NP, NP-hardness. But I can't understand how to interpret $BPP^{NP}$. I believe it means "BPP with an NP oracle" but how should I interpret that?

Does this mean that members of this class are problems for which there exist randomized algorithms that run in polynomial time but which can call another algorithm that can solve any problem in NP in constant time? If so, how is this different from just having an algorithm that can solve any problem in NP in constant time?


You should think of this as the class of problems who lie in $BPP$, but in a new (relativised) world where the model of computation is slightly different. Turing machines now have an additional query tape and three new special states, $q_{\text{query}},q_{\text{yes}},q_{\text{no}}$. Upon entering the state $q_\text{query}$, if the contents of the query tape is $s\in\Sigma^*$, then the machine goes to either the yes or no state depending on whether or not $s\in SAT$.

The key point is that nothing changes in the BPP part, the only thing different is the computational model. This actually changes everything, but luckily we can integrate the oracle to the standatd Turing machine without changing basic notions such as time/space complexity. This allows us to talk about classes such as $P, NP, BPP$ in the new model (we can define them in exactly the same way).

Note that we don't have a general definition of $A^B$ for two complexity classes $A, B$. We use this notation when $A$ has a natrual extension to the relativised (oracle) world.

Additionally, to define our model of computation precisely we need to specify exactly what is the oracle (we need to define the transition function from $q_{\text{query}})$. Thus, we can't have an algorithm solve every NP problem in a single step, we need to choose a problem in order to specify a well defined behavior for the machine. It is not hard to show that for every two NP complete languages $L,L'$ it holds that $\mathsf{BPP^L=BPP^{L'}}$. So when we write $BPP^{NP}$ we mean languages having a BPP machine with access to a SAT oracle (or any other NP complete language of your choosing). In cases where the definition of $A^B$ might depend on the exact choosing of the oracle, statements involving $A^B$ usually hide a universal quantifier on the oracle, and should be read as "for all $o\in B$ ...".

  • $\begingroup$ Thank you. So is $NP \subseteq BPP^{NP}$? If not, can you give a simple example of a problem in $NP$ which is not in $ BPP^{NP}$? $\endgroup$ – Anush Jun 11 '18 at 12:34
  • $\begingroup$ It seems from your first paragraph that we can solve SAT in $BPP^{NP}$ by reading in an instance of it and then going into the special state $q_{query}$. This presumably just takes the time to read in the problem. Is that right? $\endgroup$ – Anush Jun 11 '18 at 12:39
  • 2
    $\begingroup$ I suggest that you take some time to digest this answer. I am certain that afterwards you will be able to answer this yourself (I will obviously happily help to clarify things once you have done so). $\endgroup$ – Ariel Jun 11 '18 at 12:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.