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$
  • 1
    $\begingroup$ It might help if you tell us which paper you're quoting. $\endgroup$ – Robin Kothari Jun 18 '11 at 13:44
  • 2
    $\begingroup$ @Robin Kothari: It is "Notions of reducibility between cryptographic primitives" - 2004 (springerlink.com/content/q3jp67gnpkhkn38q) $\endgroup$ – M. Alaggan Jun 18 '11 at 18:55
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
    $\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$ – Robin Kothari Jun 18 '11 at 20:33
  • $\begingroup$ Do you have any idea whether PP^(PP^A) is the same as (PP^PP)^A ? $\endgroup$ – M. Alaggan Jun 18 '11 at 22:45

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.