8
$\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$.
Improve this question
$\endgroup$
11
  • 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, 2014 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, 2014 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, 2014 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, 2014 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, 2014 at 18:28

2 Answers 2

Reset to default
11
$\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.)

Improve this answer
$\endgroup$
4
  • $\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, 2014 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, 2014 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, 2014 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, 2014 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'}$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Turbo
    Oct 5, 2020 at 18:39

Your Answer

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

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