I tried to prove or disprove that pp is closed under cook reductions. anyone has a idea or link to a answer?


closed as unclear what you're asking by David Richerby, Evil, Juho, Tom van der Zanden, Gilles Jul 11 '16 at 12:14

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.


PH $\subseteq$ PPP ​ is known to hold, so if PP is closed under Cook reductions
then ​ PH $\subseteq$ PPP $\subseteq$ PPPP $\subseteq$ PP . ​ ​ ​ ​ ( PH $\subseteq$ PP ​ is not known to hold.)

( PP ≠ PSPACE ​ is not known to hold.)

See the Counting Hierarchy.

  • $\begingroup$ i don't sure if i understand your question. you said it's a open question? $\endgroup$ – evyatar Jun 21 '16 at 14:19
  • $\begingroup$ I didn't ask a question here. ​ ​ $\endgroup$ – user12859 Jun 21 '16 at 22:37
  • $\begingroup$ i meam your answer $\endgroup$ – evyatar Jun 22 '16 at 12:20

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