1
$\begingroup$

We know if every language in $EXP$ has polysize circuits, then $P\neq NP$ and $EXP=PSPACE=\Sigma_2^P\cap\Pi_2^P$.

  1. If every language in $PSPACE$ has polysize circuits, then does it give anything (note if it gave does $P\neq PSPACE$ then this would give $P\neq PSPACE$ unconditionally since $P\subseteq P/poly$ and $P=PSPACE\implies PSPACE\subseteq P/poly\implies P\neq PSPACE$ a contradiction)?

If every language in $PSPACE$ is in $BPP$ then $BPP=\Sigma_2^P\cap\Pi_2^P=PSPACE\neq EXP\not\subseteq P/poly$.

If every language in $PSPACE$ is in $RNC$ then $NC\neq P=PSPACE=RNC=BPP=\Sigma_2^P\cap\Pi_2^P\neq EXP$ (note $NC=PSPACE$ is not possible unconditionally).

  1. If every language in $PSPACE$ is in $BPP$ or is in $RNC$ do they give anything beyond?
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.