Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Non-Uniformity is quite powerful in complexity theory.

For example: BPP is a subset of P/poly. If NP is a subset of P/poly, then the polynomial hierarchy collapses to Sigma^2.


Is there a good survey on the power/limitations of non-uniformity?


share|improve this question
You should also consider asking this question at [cstheory.stackexchange.com]. –  Niel de Beaudrap Oct 6 '11 at 22:29
Why is this not appropriate for the complexity theory subsection of math overflow? It's asking for a survey of a research topic. –  nonuniformity Oct 6 '11 at 23:31
@nonuniformity: If you're right that "this is not appropriate for the complexity theory subsection", then the only reason I could think of for that would be that essentially every general CS theory paper was such a survey. –  Ricky Demer Oct 6 '11 at 23:44
I think Niel's point is that there is larger complexity theory audience on cstheory and you might get more answers, not that it is not appropriate here. (pay attention to "also" in his comment). I am not sure, but probably we have had a question similar to this on cstheory sometime ago. –  Kaveh Oct 7 '11 at 1:19
ps: it is better to register an account so you can edit your posts in future. –  Kaveh Oct 7 '11 at 1:20
show 1 more comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.