4
$\begingroup$

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?

1 Answers 1

2

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

  • 0
    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?2012-11-10
  • 0
    @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?2012-11-10
  • 0
    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?)2012-11-10
  • 0
    @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}}$.2012-11-11
  • 0
    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?2012-11-12
  • 0
    @ComplexityTheoryStudent: There really isn't much of a difference here. In attempting to construct the set $B$, in the case where $M_i$ rejects we must make sure that there is _never_ a lucky run. This involves looking at all possible runs, which might as well be taken to be parallel. I used this language because it was easier for me to think about it correctly and I believe that it is easier to understand in this case. (At other times the "lucky guess" heuristic is better.)2012-11-12