1
$\begingroup$

$PP\subseteq P/poly\implies PP=\Sigma_2\cap\Pi_2$ and $EXP\subseteq P/Poly\implies EXP=PP$ $=CH=MA$.

  1. If $PP\subseteq P/poly$ then can $PP=\Sigma_2\cap\Pi_2=MA$ hold? Are there difficulties showing this?

  2. What evidence do we have for $EXP\not\subseteq PP/poly$ (such as derandomization results)?

  3. Is there any consequence to derandomization or polynomial hierarchy if $PP^{PP}=PP=CH$ holds? Note $\oplus P$, $AWPP$ and $BPP$ are low for themselves.

  4. If $P=BPP$ then $BPP$ has a complete language $\mathcal L$. Note that for $BPP$ we need probability $\frac12+\epsilon$ acceptance probability where $\epsilon\in(0,\frac12)$ is fixed while in $PP$ we let $\epsilon$ depend on input size in an inverse exponential way. It seems that there should not be any relation between the complete language for $PP$ and $\mathcal L$. However given similarities in definitions we cannot rule it out. Do we know that we can for sure tell there are no relations between the complete languages?

$\endgroup$

0

Your Answer

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