I know that BPP is in P/poly.

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


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


  • 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 Oct 7 '11 at 7:18

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.