8

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$.
Community
  • 1
vzn
  • 11,014
  • 2
  • 31
  • 64
  • 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. – Suresh Venkat Mar 21 '14 at 16:40
  • 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 Mar 21 '14 at 16:42
  • 4
    If $B'$ is too weak (e.g. $B' \in P$) then the implication $\Rightarrow$ is true. – Marzio De Biasi Mar 21 '14 at 16:55
  • 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 Mar 21 '14 at 17:02
  • 3
    If it is large enough that $NP^B=B$ (e.g. PSpace) then it is vacuously true. – Kaveh Mar 21 '14 at 17:06
  • 1
    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 Mar 21 '14 at 17:12
  • 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}$. – Joshua Grochow Mar 21 '14 at 18:28
  • @Josh yes, I know, I should have stated it more carefully. – Kaveh Mar 21 '14 at 19:29
  • 1
    @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 Mar 21 '14 at 22:46
  • @Sasho, it asks for languages and I meant languages like TQBF. – Kaveh Mar 22 '14 at 03:00
  • btw all the dynamic behind this proof & answers remind me of this other question proving lower bounds by proving upper bounds 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 Mar 24 '14 at 21:15

2 Answers2

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

Sasho Nikolov
  • 18,189
  • 2
  • 67
  • 115
  • 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 Oct 05 '20 at 18:39
11

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

Joshua Grochow
  • 37,260
  • 4
  • 129
  • 228
  • By the way, Baker-Gill-Solovay attribute the EXP upper bound to Ladner (near the bottom of p. 436). – Joshua Grochow 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? – Sasho Nikolov Mar 21 '14 at 22:40
  • 2
    @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 Mar 22 '14 at 20:30