Baker, Gill, Solovay - construction of oracle B such that P^B != NP^B

I have some questions about Baker, Gill, Solovay proof of the existence of an oracle such that P^B != NP^B. The proof can be found in Siam Journal of Computing, 4:432-442, 1975 [219].

• Why Isn't this construction considered a counterexample to P = NP? And if it is not, can it be strengthened into one? It seems tome that we have constructed a languge recognizable in NP time but not in P time.

• In the proof there is the sentence "If P_i^B(i) accepts 0^n, then place no string into B at this stage." How can this possibly happen?

I figured that, since B is intially empty, the oracle B(i) ALWAYS rejects. So the only reason why P_i would accept is some reason OTHER than a question to B(i). Please correct me if I am wrong.

The proof in question is verbatim reproduced here. The original paper is here.

• You previously asked your first question earlier at cs.stackexchange.com/q/113595/755. It would be nice to recognize the answer you already got and identify more specifically what your specific confusion with it is. – D.W. Sep 24 at 23:16
• I was given the answer that it IS NOT a counterexample. Now I am asking WHY it is not a counterexample. If you want to participate in this discussion it would be more productive if you answered the question as clearly as you can instead of critiquing how people are asking a question. – Newberry Sep 26 at 5:12

As the original paper is showing a lot more, I use this one at page 69-70, Theorem 3.9, as this is the proof I also know.

As you can see there, the complete statement of Baker, Gill, Solovay is:

There exist oracles $$A, B$$ s.t. $$P^A = NP^A$$ and $$P^B \neq NP^B$$

The second oracle cannot be considered a counterexample for $$P = NP$$ because you cannot "divide" by B so to say. Constructing a oracle language $$L^A$$ out of a "normal" language $$L$$ is not that easy. The languages $$P^B$$ and $$NP^B$$ behave completely different than $$P$$ and $$NP$$. To show you an example for this: Even if $$P=NP$$ is true, the statement $$P^B \neq NP^B$$ is still valid. This shows how different $$P,NP$$ and $$P^B, NP^B$$ behave.

It seems to me that we have constructed a language recognizable in NP time but not in P time.

Be careful here. It is shown that unary language $$U_B$$ can be recognized by a $$NP^B$$-TM, not by a $$NP$$-TM. Again, this is because Oracle-Languages/TMs behave completely different than their "normal" counterparts. If you want to recognize $$U_B$$ in $$NP$$ without the oracle, you have to do a lot more work as you could guess a word $$w$$ of length $$i$$ in poly. time, but you cannot decide $$w \in B$$ that easy, as we have no clue by BGS if $$B \in NP$$ or not.

And if it is not, can it be strengthened into one?

Maybe yes, maybe not. As this would solve $$P=NP?$$, which is unknown, it is unknown if you could strengthen it or not.

In the proof there is the sentence "If $$P_i^{B(i)}$$ accepts $$0^n$$, then place no string into B at this stage." How can this possibly happen?

As you just simulate all TMs in $$P_i^{B(i)}$$ and don't change them, you cannot change whether the TM accepts or not. For example, the TM that accepts all words is in $$P$$, so it also is in $$P^B$$, so it will be simulated at some point. Then, your case will happen. Of course, this TM will not call the oracle once.

Edit 3:

Now I want to convince you that your Algorithm does not run in $$NP$$-time. I can't convince you by now that really $$B \not \in NP$$, but I think I can convince you now at least that this algorithm does not gives us $$B \in NP$$.

Let's try to formulate your algorithm as an $$NP$$-TM that decides $$w \in B$$ (using original BGS, Theorem 3 now):

1. Guess $$i$$ s.t. $$M_i^B(1^{|w|})$$ is the poly-TM where $$n:=|w|$$ is choosen. See that $$M_i$$ has access to oracle $$B$$. Guessing $$i$$ is possible because $$i\leq n$$ as each stage needs a unique $$n$$. However, can we verify that $$i$$ is right? To do so, we might have to really build $$B$$ from stage $$i=0$$, which would take to long.

2. Simulate $$M_i(1^{|w|})$$ for $$2^n/10$$ time. I'm not sure whether we can do this. We don't know if $$M_i$$ is a poly-time TM, so we can't really guess a polynomial $$p : \mathbb{N} \rightarrow \mathbb{N}$$ so it could really run for $$2^n/10$$ time as we enumerate all TM's so e.g. also the $$EXP$$-hard ones. Can you find a fix for this? If so, I will re-edit this answer to describe the next steps. Using original BGS now:

2. Simulate $$M_i^B(1^{|w|})$$ for $$p(|w|)$$ time. We can guess the polynomial $$p$$ in $$NP$$-time. However, can we verify that $$p$$ is the right polynomial? We cannot assume that it's right and I can't find an easy way to do this. But here comes the problem: Can we really simulate $$M_i^B(1^{|w|})$$ in poly. time? I want to convince you that this is not the case.

2.1. If $$M_i^B(1^{|w|})$$ writes $$x_B$$ on the oracle tape and asks $$x_B \in B?$$, what can we do in $$NP$$ without the oracle? We can only start another simulation, guess another $$i'$$ s.t. stage $$i'$$ takes $$n':=|x_B|$$ and simulate $$M_{i'}^B(1^{|x_B|})$$.

However, how many such new simulations do we have to do in the worst case? $$M_i^B(1^{|w|})$$ with running time $$p(|w|)$$ could ask the oracle $$p(|w|)$$ questions of length $$p(|w|)$$. Let's look at some arbitrary question at step $$j$$ now. Let the asked question in step $$j$$ be $$x_B \in B?$$. Now, we have to guess $$i'$$ s.t. $$n':=|x_B|$$ and simulate $$M_{i'}^B(1^{|x_B|})$$. Let $$p'(|x_B|)$$ be the running time of $$M_{i'}^B(1^{|x_B|})$$. Now, in the worst case, $$M_{i'}^B(1^{|x_B|})$$ asks the oracle $$B$$ in every of the $$p'(|x_B|) = p'(p(|w|))$$ steps again a question of length $$p'(|x_B|) = p'(p(|w|))$$. And this can go on and on.

In the end, we have build a tree with the vertex degree being $$O(p''(|w|))$$ for some polynomial $$p''$$. The depth of this tree can be pretty huge, because $$i$$ could equal $$i'$$. Let's assume just for simplicity that in each step $$j$$ we asked each stage $$k \in \{1,\cdots,n\}$$ exactly one question. Then we have depth $$n$$ for each path from the root to some leaf in the tree. Therefore, to answer the initial question $$w \in B?$$, we have to look at each of the $$O(p''(|w|))^n$$ verticies. Clearly, this can only be done in exponentioal time and not in polynomial time, because we have a exponention number of vertecies w.r.t $$|w|$$. Therefore, the algorithm does not run in $$NP$$-time.

• “you could guess a word w of length i in poly. time, but you cannot decide w∈B that easy, as we have no clue by BGS if B∈NP or not. ” We have just constructed the set B. Why cannot we organize it into a two-dimensional table indexed by string length n and 0 <= j < 2^n? Then given n you just guess j. – Newberry Sep 25 at 20:52
• I think the problem with your idea is that $B$ is not part of the input. We showed how $B$ is defined, but to check whether $w\in B?$ with is harder. This basically means that we have to set up all stages of $B$ until stage $j$ where the choosen $n$ is equal to $|w|$. And then we have to simulate $M_i$ for $2^n/10$ steps, which is longer than any polynomial w.r.t. the input size $|w|=n$. Using a table, I think, cannot be done because $B$ is not part of the input and it cannot be hidden inside the TM-Description because $B$ is an infinite sized language, so the table would be infinitely large – Niklas Wünsche Sep 27 at 12:46
• The set B is infinite but it has a FINITE algorithmic description. Given a string of length n the NP recognizer can simply simulate P_i for p_i(n) steps. If P_i accepts it rejects, if not it accepts. – Newberry Sep 27 at 20:13
• I see your point now, thank you! I think the problem with simulating $P_i$ here is that $P_i$ takes $n$ as the unary input, so $1^n$. As a number encoded in binary $n$ bits can have a value of $2^n$, it takes exponentially long to write out the unary string $1^n$ of $n$. You also cannot guess $n$ in unary in $NP$ because this also takes $2^n$ steps. I think this is where this argument of simulating $P_i$ breaks. – Niklas Wünsche Sep 29 at 13:59
• No, 1^n is just a string of length n. It is not a number. In fact in the original BGS paper it is 0^n. – Newberry Sep 29 at 23:45