Sign up ×

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?

share|cite|improve this question

1 Answer 1

up vote 2 down vote accepted

I believe that the following is what breaks in translating the deterministic proof to non-determinism.

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.)

share|cite|improve this answer
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? – Arthur Fischer 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}}$. – Arthur Fischer Nov 11 '12 at 8:23
I'd like to ask one more thing to clarify your answer. We have two parallel ways to model non-deterministic Turing machines. In your answer you use the one where all the non-deterministic branches are evaluated in parallel. On the other hand, sometimes we assume that the machine luckily guesses the right branch and only evaluates this one (eg we would have polynomial number of queries even for NTM). Why is it correct to use the model where all branches are evaluated in parallel in this case? – Complexity Theory Student Nov 12 '12 at 13:45

Your Answer


