<p>For question 2, you can take any $B' \in \mathsf{PH}$ (this means you cannot bring down the $B$ in the BGS result down from $\mathsf{EXP}$ to $\mathsf{PH}$ without resolving the <em>big question</em>). </p>

<p>Clearly for any $B'$, $P \subseteq \mathsf{P}^{B'} \subseteq \mathsf{NP}^{B'}$. Let $B' \in \Sigma_i^{\mathsf{P}}$. Recall that, by the definition of the Polynomial Hierarchy, $\mathsf{P}^{B'} \subseteq\mathsf{P}^{\Sigma_i^{\mathsf{P}}} = \Delta_{i+1}^{\mathsf{P}}$ and $\mathsf{NP}^{B'} \subseteq {\mathsf{NP}}^{\Sigma_i^{\mathsf{P}}} = \Sigma_{i+1}^{\mathsf{P}}$. If $\mathsf{P} =\mathsf{NP}$, then $\mathsf{P} = \Delta_{i+1}^{\mathsf{P}} = \Sigma_{i+1}^{\mathsf{P}}$ for all $i$, and, therefore $\mathsf{P} = \mathsf{P}^{B'} = \mathsf{NP}^{B'}$.</p>

CC BY-SA 4.0
2020-10-05T18:39:06.953Z
If say SAT has a polysized linear program then how can it make sense such a $B$ still works? By makes sense I mean 'convince myself' of the result.
Turbo
CC BY-SA 3.0
2014-03-21T17:22:28.750Z
2014-03-21T22:35:30.583Z
2014-03-21T22:35:30.583Z
Sasho Nikolov
<p>For question 1, the BGS construction can be performed in exponential time, so you can construct such $B \in \mathsf{EXP}$.</p>

<p>(For question 2: Sasho Nikolov's answer was originally only for $\mathsf{\Sigma_k P}$-complete languages, and I pointed out that one can also take any $B' \in \mathsf{NP} \cap \mathsf{coNP}$, since $\mathsf{NP}^{\mathsf{NP} \cap \mathsf{coNP}} = \mathsf{NP}$. But Sasho's updated answer subsumes this case.)</p>

CC BY-SA 3.0
2014-03-21T18:27:34.280Z
By the way, Baker-Gill-Solovay attribute the EXP upper bound to Ladner (near the bottom of p. 436).
Joshua Grochow
CC BY-SA 3.0
2014-03-21T19:02:32.100Z
ok yeah what about anything "smaller" than EXP? apparently an open question... for the B constructed in the BGS proof, can B∈ {smaller (than EXP) classes given implying P≠NP} be _ruled out_?
vzn
CC BY-SA 3.0
2014-03-21T22:40:11.283Z
Josh, I think with a very small variation in my argument, any $B'$ in $\mathsf{PH}$ suffices. Please check if it makes sense, I've made silly mistakes with oracle results before. Also, any idea if we can something about $B' \in \mathsf{PP}$? Counting Hierarchy?
Sasho Nikolov
CC BY-SA 3.0
2014-03-22T20:30:09.167Z
@Sasho: You're right - can't believe I missed that before! I don't know about extending it to $\mathsf{PP}$ or $\mathsf{CH}$ - this is probably related to Regan's class $\mathsf{H}$ (see the comments on this question: http://cstheory.stackexchange.com/questions/5463/can-one-amplify-p-np-beyond-p-ph), which is defined as the set of $L$ such that $L \in \mathsf{P}^O$ for every oracle $O$ such that $\mathsf{P}^O=\mathsf{NP}^O$. It's known that $\mathsf{H}$ is contained in alternations-time $(O(\log \log n), poly(n))$.
Joshua Grochow
CC BY-SA 3.0
2014-03-21T18:09:42.000Z
2014-03-22T20:32:16.060Z
2014-03-22T20:32:16.060Z
Joshua Grochow
<p>A recent question asks <a href="https://cstheory.stackexchange.com/questions/21590/is-relativization-well-defined">whether relativization is well-defined</a>. This question wonders how to put one use of it on firmer ground. </p>

<blockquote>
  <ol>
  <li>In the <a href="http://zoo.cs.yale.edu/classes/cs468/BGS.pdf" rel="nofollow noreferrer">BGS 1975 proof</a> that there exists a language $B$ such that $P^B \neq NP^B$. To best available knowledge, what complexity class is $B$ in?</li>
  <li>Fill in the blank ("$?$") if possible, or analyze as best possible: if there existed a $B'$ in class "$?$" such that $P^{B'} \neq NP^{B'}$, then $P \neq NP$.</li>
  </ol>
</blockquote>

CC BY-SA 3.0
2014-03-21T16:40:35.383Z
I think the point of BGS is that that no answer to Q2 exists (i.e no relativized proof will imply that P $\ne$ NP.
Suresh Venkat
CC BY-SA 3.0
2014-03-21T16:42:45.217Z
that seems to be the typical interpretation but wouldnt the implication hold if $B'$ is "weak enough"—and is there any _nontrivially weak_ $B'$ for which it holds... ie it seems to be a lower/upper bounds/reductions type question...
vzn
CC BY-SA 3.0
2014-03-21T16:55:43.197Z
If $B'$ is too weak (e.g. $B' \in P$) then the implication $\Rightarrow$ is true.
Marzio De Biasi
CC BY-SA 3.0
2014-03-21T17:02:57.940Z
right, so is it ever true when $B'$ is _more complex_ than P, and _exactly how much more complex?_ is $B$ "slightly more complex" than P? and is it always the case that the implication doesnt hold for anything "slightly more complex than P"? in other words is the $B$ that BGS worked with definitive, or could there be other $B'$ worth looking at...
vzn
CC BY-SA 3.0
2014-03-21T17:06:35.583Z
If it is large enough that $NP^B=B$ (e.g. PSpace) then it is vacuously true.
Kaveh
CC BY-SA 3.0
2014-03-21T17:12:43.977Z
ps: B in BGS is based on simulating P machines so its complexity class should contain the universal problem for P and the best known upperbound for it if I remember correctly is Exp.
Kaveh
CC BY-SA 3.0
2014-03-21T18:28:18.250Z
@Kaveh: "Large enough" isn't quite sufficient (though what you say for $\mathsf{PSPACE}$ is certainly true). For that particular argument, you also want self-low, e.g. $PSPACE^{PSPACE} = PSPACE$. In contrast, $EXP^{EXP}$ contains $EEXP$, so we get $P^{EXP} = EXP$, but the naive upper bound for $NP^{EXP}$ is $EXP^{EXP} \supseteq EEXP$. A slightly less naive upper bound gives $NP^{EXP} \subseteq NEXP$, but we still don't get $NP^{EXP}=EXP=P^{EXP}$.
Joshua Grochow
CC BY-SA 3.0
2014-03-21T19:29:01.040Z
@Josh yes, I know, I should have stated it more carefully.
Kaveh
CC BY-SA 3.0
2014-03-21T22:46:35.380Z
@Kaveh the question (as I read it) asks about classes $\mathsf{C}$ such that *for any language* $B \in \mathsf{C}$, $\mathsf{P}^B \neq \mathsf{NP}^B \Rightarrow \mathsf{P} \neq \mathsf{NP}$. I don't think that's known to be true for $\mathsf{PSPACE}$: only for the class of $\mathsf{PSPACE}$-complete problems.
Sasho Nikolov
CC BY-SA 3.0
2014-03-22T03:00:25.067Z
@Sasho, it asks for languages and I meant languages like TQBF.
Kaveh
CC BY-SA 3.0
2014-03-24T21:15:15.453Z
btw all the dynamic behind this proof & answers remind me of this other question [proving lower bounds by proving upper bounds](http://cstheory.stackexchange.com/questions/3229/) and it appears basically that if the upper bound on B can be made "tight enough" its equivalent to P≠NP (ie "lower upper bound on B implies higher lower bound on NP").
vzn
<cc.complexity-theory><oracles><p-vs-np><relativization>
Baker Gill Solovay $P^B \ne NP^B$ relativization, what class is $B$ in?
vzn
# Baker Gill Solovay $P^B \ne NP^B$ relativization, what class is $B$ in?

(Asked by: username_0 on 2014-03-21)

A recent question asks [whether relativization is well-defined](https://cstheory.stackexchange.com/questions/21590/is-relativization-well-defined). This question wonders how to put one use of it on firmer ground.

> 1. In the [BGS 1975 proof](http://zoo.cs.yale.edu/classes/cs468/BGS.pdf) that there exists a language $B$ such that $P^B \neq NP^B$. To best available knowledge, what complexity class is $B$ in?
> 2. Fill in the blank ("$?$") if possible, or analyze as best possible: if there existed a $B'$ in class "$?$" such that $P^{B'} \neq NP^{B'}$, then $P \neq NP$.

**Tags:** cc.complexity-theory, oracles, p-vs-np, relativization
> **Comments:**
> **username_1**: I think the point of BGS is that that no answer to Q2 exists (i.e no relativized proof will imply that P $\ne$ NP.  
> **username_0**: that seems to be the typical interpretation but wouldnt the implication hold if $B'$ is "weak enough"—and is there any _nontrivially weak_ $B'$ for which it holds... ie it seems to be a lower/upper bounds/reductions type question...  
> **username_2**: If $B'$ is too weak (e.g. $B' \in P$) then the implication $\Rightarrow$ is true.  
> **username_0**: right, so is it ever true when $B'$ is _more complex_ than P, and _exactly how much more complex?_ is $B$ "slightly more complex" than P? and is it always the case that the implication doesnt hold for anything "slightly more complex than P"? in other words is the $B$ that BGS worked with definitive, or could there be other $B'$ worth looking at...  
> **username_3**: If it is large enough that $NP^B=B$ (e.g. PSpace) then it is vacuously true.  
> **username_3**: ps: B in BGS is based on simulating P machines so its complexity class should contain the universal problem for P and the best known upperbound for it if I remember correctly is Exp.  
> **username_4**: @Kaveh: "Large enough" isn't quite sufficient (though what you say for $\mathsf{PSPACE}$ is certainly true). For that particular argument, you also want self-low, e.g. $PSPACE^{PSPACE} = PSPACE$. In contrast, $EXP^{EXP}$ contains $EEXP$, so we get $P^{EXP} = EXP$, but the naive upper bound for $NP^{EXP}$ is $EXP^{EXP} \supseteq EEXP$. A slightly less naive upper bound gives $NP^{EXP} \subseteq NEXP$, but we still don't get $NP^{EXP}=EXP=P^{EXP}$.  
> **username_3**: @Josh yes, I know, I should have stated it more carefully.  
> **username_5**: @Kaveh the question (as I read it) asks about classes $\mathsf{C}$ such that *for any language* $B \in \mathsf{C}$, $\mathsf{P}^B \neq \mathsf{NP}^B \Rightarrow \mathsf{P} \neq \mathsf{NP}$. I don't think that's known to be true for $\mathsf{PSPACE}$: only for the class of $\mathsf{PSPACE}$-complete problems.  
> **username_3**: @Sasho, it asks for languages and I meant languages like TQBF.  
> **username_0**: btw all the dynamic behind this proof & answers remind me of this other question [proving lower bounds by proving upper bounds](http://cstheory.stackexchange.com/questions/3229/) and it appears basically that if the upper bound on B can be made "tight enough" its equivalent to P≠NP (ie "lower upper bound on B implies higher lower bound on NP").  

---

## 2 answers

### Answer by username_4 on 2014-03-21. Score: 11 | Accepted answer

For question 1, the BGS construction can be performed in exponential time, so you can construct such $B \in \mathsf{EXP}$.

(For question 2: Sasho Nikolov's answer was originally only for $\mathsf{\Sigma\_k P}$-complete languages, and I pointed out that one can also take any $B' \in \mathsf{NP} \cap \mathsf{coNP}$, since $\mathsf{NP}^{\mathsf{NP} \cap \mathsf{coNP}} = \mathsf{NP}$. But Sasho's updated answer subsumes this case.)

> **Comments:**
> **username_4**: By the way, Baker-Gill-Solovay attribute the EXP upper bound to Ladner (near the bottom of p. 436).  
> **username_0**: ok yeah what about anything "smaller" than EXP? apparently an open question... for the B constructed in the BGS proof, can B∈ {smaller (than EXP) classes given implying P≠NP} be _ruled out_?  
> **username_5**: Josh, I think with a very small variation in my argument, any $B'$ in $\mathsf{PH}$ suffices. Please check if it makes sense, I've made silly mistakes with oracle results before. Also, any idea if we can something about $B' \in \mathsf{PP}$? Counting Hierarchy?  
> **username_4**: @Sasho: You're right - can't believe I missed that before! I don't know about extending it to $\mathsf{PP}$ or $\mathsf{CH}$ - this is probably related to Regan's class $\mathsf{H}$ (see the comments on this question: http://cstheory.stackexchange.com/questions/5463/can-one-amplify-p-np-beyond-p-ph), which is defined as the set of $L$ such that $L \in \mathsf{P}^O$ for every oracle $O$ such that $\mathsf{P}^O=\mathsf{NP}^O$. It's known that $\mathsf{H}$ is contained in alternations-time $(O(\log \log n), poly(n))$.  

---

### Answer by username_5 on 2014-03-21. Score: 11

For question 2, you can take any $B' \in \mathsf{PH}$ (this means you cannot bring down the $B$ in the BGS result down from $\mathsf{EXP}$ to $\mathsf{PH}$ without resolving the *big question*).

Clearly for any $B'$, $P \subseteq \mathsf{P}^{B'} \subseteq \mathsf{NP}^{B'}$. Let $B' \in \Sigma\_i^{\mathsf{P}}$. Recall that, by the definition of the Polynomial Hierarchy, $\mathsf{P}^{B'} \subseteq\mathsf{P}^{\Sigma\_i^{\mathsf{P}}} = \Delta\_{i+1}^{\mathsf{P}}$ and $\mathsf{NP}^{B'} \subseteq {\mathsf{NP}}^{\Sigma\_i^{\mathsf{P}}} = \Sigma\_{i+1}^{\mathsf{P}}$. If $\mathsf{P} =\mathsf{NP}$, then $\mathsf{P} = \Delta\_{i+1}^{\mathsf{P}} = \Sigma\_{i+1}^{\mathsf{P}}$ for all $i$, and, therefore $\mathsf{P} = \mathsf{P}^{B'} = \mathsf{NP}^{B'}$.

> **Comments:**
> **username_6**: If say SAT has a polysized linear program then how can it make sense such a $B$ still works? By makes sense I mean 'convince myself' of the result.  

---

