3
$\begingroup$

I know that BPP is in P/poly.

I know that if NP is in P/poly then $PH = \Sigma^2_p$

Question:

Is there a good survey on the power of non-uniformity? I'm basically looking for a list of known results about non-uniformity.

Thanks!

Improve this question
$\endgroup$
1
  • 5
    $\begingroup$ Hi and welcome to cstheory. This question is cross-posted on MO, please read our FAQ and the policy on cross-posting. Also although it is not required I encourage you to register an account and use a real name. $\endgroup$
    – Kaveh
    Commented Oct 7, 2011 at 7:18

0

Reset to default

Your Answer

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