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.

  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Sep 24, 2019 at 23:16
  • $\begingroup$ 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. $\endgroup$
    – Newberry
    Sep 26, 2019 at 5:12

1 Answer 1


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.

  • $\begingroup$ “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. $\endgroup$
    – Newberry
    Sep 25, 2019 at 20:52
  • $\begingroup$ 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 $\endgroup$ Sep 27, 2019 at 12:46
  • 1
    $\begingroup$ 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. $\endgroup$
    – Newberry
    Sep 27, 2019 at 20:13
  • $\begingroup$ 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. $\endgroup$ Sep 29, 2019 at 13:59
  • 1
    $\begingroup$ 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. $\endgroup$
    – Newberry
    Sep 29, 2019 at 23:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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