11
$\begingroup$

I would like to know if there exists a relativized world where ${\bf P^A}={\bf NP^A}\not = {\bf PP^A}$. I am also interested to know if there exists a relativized world where ${\bf P^B} \not = {\bf NP^B} = {\bf PP^B}$.

$\endgroup$
  • 7
    $\begingroup$ I have a blog post "extreme oracles" which has a list of oracle results from which many others follow, including the two you ask. blog.computationalcomplexity.org/2005/08/extreme-oracles.html $\endgroup$ – Lance Fortnow Mar 30 '13 at 19:29
  • 2
    $\begingroup$ @Lance: Damn, just saw that after posting my answer! Well, maybe the OP will still find my "homemade" constructions useful. $\endgroup$ – Scott Aaronson Mar 30 '13 at 19:34
14
$\begingroup$

I don't know a reference, but I think both of these should be doable.

For your first oracle: for starters you'll want an oracle (call it $A_1$) that encodes exponentially-large $MAJORITY$ instances, and that thereby separates both $P^{A_1}$ and $NP^{A_1}$ from $PP^{A_1}$. Then you want a second oracle (call it $A_2$) that encodes the solutions to all $PH^{A_1}$ problems, in a "staggered" fashion such that accessing the $k^{th}$ level of the hierarchy requires queries of size (say) $n^k$ (and hence you can only get a constant number of alternations in polynomial time). This second oracle should cause $P^{A_1,A_2} = NP^{A_1,A_2} = PH^{A_1,A_2} = PH^{A_1}$. (Note that $A_2$ is just an "outer" layer, meaning that any queries to $A_2$ can be simulated by $PH^{A_1}$ queries.) Finally, you'll want to appeal to Yao's and Hastad's $AC^0$ lower bounds (i.e., the switching lemma) to show that a $PH^{A_1}$ machine still can't solve the $MAJORITY$ instances in $A_1$, and therefore $PP^{A_1}$ (and certainly $PP^{A_1,A_2} = PP^{PH^{A_1}}$) remains larger.

For your second oracle, you'll want to construct $B$ in such a way that you need to solve an $NP$ search problem in order to "unlock" a part of the oracle string that then boosts your power up to $PSPACE$. (Here we exploit the fact that $NP^{PSPACE}$ and $PP^{PSPACE}$ are both $PSPACE$.) A subtlety is that the secret part of the oracle can't just decide an unrelativized $PSPACE$-complete language: it also needs to provide the answers to $PSPACE$ computations that query $B$ itself. Fortunately, it's known how to achieve that in stages, avoiding the circularity: basically, you encode the outputs of the $PSPACE^B$ machines that only query $B$ on inputs of size $p(n)$ or less, in a part of $B$ that requires queries of size $>p(n)$ to access, and that's therefore "out of reach" for those machines (but not for other $PSPACE^B$ machines). Meanwhile, the $P^B$ machines are left "completely in the dark" by all this.

$\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.