7
$\begingroup$

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$.
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Suresh Venkat Mar 21 '14 at 16:40
  • 4
    $\begingroup$ If $B'$ is too weak (e.g. $B' \in P$) then the implication $\Rightarrow$ is true. $\endgroup$ – Marzio De Biasi Mar 21 '14 at 16:55
  • 3
    $\begingroup$ If it is large enough that $NP^B=B$ (e.g. PSpace) then it is vacuously true. $\endgroup$ – Kaveh Mar 21 '14 at 17:06
  • 1
    $\begingroup$ 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. $\endgroup$ – Kaveh Mar 21 '14 at 17:12
  • 4
    $\begingroup$ @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}$. $\endgroup$ – Joshua Grochow Mar 21 '14 at 18:28
12
$\begingroup$

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

$\endgroup$
  • $\begingroup$ By the way, Baker-Gill-Solovay attribute the EXP upper bound to Ladner (near the bottom of p. 436). $\endgroup$ – Joshua Grochow Mar 21 '14 at 18:27
  • $\begingroup$ 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? $\endgroup$ – vzn Mar 21 '14 at 19:02
  • $\begingroup$ 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? $\endgroup$ – Sasho Nikolov Mar 21 '14 at 22:40
  • 2
    $\begingroup$ @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))$. $\endgroup$ – Joshua Grochow Mar 22 '14 at 20:30
11
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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