2
$\begingroup$

It is well known that $\mathsf{\#P}$ is non-adaptively random self-reducible, with the common proof given via the permanent. Feigenbaum and Fortnow showed that this implies $\mathsf{PP}$ is adaptively random self-reducible as $\mathsf{P^{\#P}=P^{PP}}$. Is it known if or can it be shown that $\mathsf{PP}$ is also non-adaptively random self-reducible?

$\endgroup$

0

Your Answer

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