# Baker Gill Solovay $P^B \ne NP^B$ relativization, what class is $B$ in?

A recent question asks whether relativization is well-defined. This question wonders how to put one use of it on firmer ground.

1. In the BGS 1975 proof 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$.
• 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. Mar 21 '14 at 16:40
• If $B'$ is too weak (e.g. $B' \in P$) then the implication $\Rightarrow$ is true. Mar 21 '14 at 16:55
• If it is large enough that $NP^B=B$ (e.g. PSpace) then it is vacuously true. Mar 21 '14 at 17:06
• 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. Mar 21 '14 at 17:12
• @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}$. Mar 21 '14 at 18:28

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

• By the way, Baker-Gill-Solovay attribute the EXP upper bound to Ladner (near the bottom of p. 436). Mar 21 '14 at 18:27
• 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
Mar 21 '14 at 19:02
• 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? Mar 21 '14 at 22:40
• @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: cstheory.stackexchange.com/questions/5463/…), 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))$. Mar 22 '14 at 20:30

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'}$.

• 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.
– Mr.
Oct 5 '20 at 18:39