# Baker-Gill-Solovay theorem

I have been trying to understand the proof of Baker-Gill-Solovay theorem as described in Complexity Theory: Modern Approach. I think I do understand most of it, but what troubles me is that let's say one can not easily see why $U_B \in NP^B$. If he rewrites the following proof about $P^B$ using non-deterministic oracle Turing machines then this seems to prove that $U_B$ is not in $NP^B$ either. Hence, there should be something in this proof that beaks if we try to use non-deterministic Turing machines. Could someone point out to me, what exactly does not work out?

-

Suppose that the non-deterministic Turing machine $M_i$ rejects according to the condition in the text. Note that this means that all runs of $M_i$ reject, and we now have to pick some string of length $n$ which $M_i$ has not queried in any run. The proof as written relies heavily on the fact that in $< 2^n$ steps a deterministic TM cannot query all strings of length $n$. But since we are talking about numerous "simultaneous" runs it is possible that all strings of length $n$ were queried in some run of $M_i$ of $< 2^n$ steps, making it impossible to choose a string as required. (If every string of length $n$ was checked in some run, then by declaring any string of length $n$ to be in $B$ would result in the "oracle" answering incorrectly in some run.)
Thanks, this seems a reasonable explanation. Could you also describe how a similar proof could be done with non-deterministic Turing machines. For example, let's say that we replace the definition of $U_B$ to mean "exactly one string of length n is in B". Is there actually a reason to expect that similar proof idea could work at all? – Complexity Theory Student Nov 10 '12 at 17:29
@ComplexityTheoryStudent: I'm not exactly certain what you are now looking for. This theorem basically says that the addition of oracles neither "collapses" nor "preserves" the complexity classes P and NP. Are you looking for something similar between NP and... something else? Or are you looking for an example of an oracle $B$ such that the class NP$^B$ has some particular property? – arjafi Nov 10 '12 at 18:36
For the follow up question: I'm only interested in the construction of B in the original proof. I'd like to use something similar to prove that for a different construction of $U_B$ we get that $U_B \notin NP^B$. For example this previous $U_B$ = {$1^n$ | exactly one string of length n is in B}. However, it confuses me if a similar construction with non-deterministic Turing machines makes sense. (Can I somehow make sure that this Turing machine can not query all the words of length n from B?) – Complexity Theory Student Nov 10 '12 at 20:07
@ComplexityTheoryStudent: It is not very enlightening, but you can get such a problem by taking a problem known not to be NP and relativising it to a subset $B$ of $\mathbb{N}$. For example, the problem of whether two regular expressions are identical is EXPTIME-complete problem (and thus not NP). Given $B\subseteq\mathbb{N}$ define $U_B$ to be the set of all $1^n$ where $n=2^k(2\ell+1)\in B$ is such that $k$ and $\ell$ encode (in some reasonable and uniform manner) identical regular expressions. Then, for example, $U_\mathbb{N}\notin NP^{\mathbb{N}}$. – arjafi Nov 11 '12 at 8:23