6
$\begingroup$

I've looked in the Zoo and it seems it is not true because $PH \subseteq P^{PP}$. Nonetheless I've passed by a paper that appears to have used a positive result. It was in the context that $f : \{0,1\}^* \mapsto \{0,1\}^*$ is a function, computable by probabilistic polynomial time oracle machine $M$ with access to an arbitrary oracle $A$. The authors say and I quote:

Its also immediate that $G^f$ ≡ $G^{M^A}$ is computable by a probabilistic polynomial time oracle machine with access to $A$.

where $G$ is a probabilistic polynomial time oracle machine.

They do it again also for $S^{N^A,M^A}$, $S,N$ being other probabilistic polynomial time oracle machine.

Update: the paper is "Notions of reducibility between cryptographic primitives" - 2004. It was in the proof of Lemma 1 of the part that "If there exists a fully-black-box reduction from a cryptographic primitive P to cryptographic primitive Q then there exists a relativizing reduction from P to Q as well." The definitions of fully-black-box and relativizing reduction is in the paper.

The question now, according to Lance Fortnow's answer that they are not equal, does that mean that this is a gap in the proof ?

$\endgroup$
2

2 Answers 2

12
$\begingroup$

Richard Beigel gives an oracle $A$ where $P^{NP^A}\not\subseteq PP^A$ which immediately gives $PP^{PP^A}\neq PP^A$.

$\endgroup$
2
$\begingroup$

The question appears to be related to the question of whether there exists an oracle relative to which the counting hierarchy CH is infinite or not. This is an open problem according to the Zoo.

$\endgroup$
2
  • 2
    $\begingroup$ PP and PP^PP are only the first two levels of the hierarchy. It's not clear that an oracle that separates these two would also show that the entire hierarchy is infinite. $\endgroup$ Jun 18, 2011 at 20:33
  • $\begingroup$ Do you have any idea whether PP^(PP^A) is the same as (PP^PP)^A ? $\endgroup$ Jun 18, 2011 at 22:45

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.