Question

Razborov and Rudich showed that any natural proof of a lower bound on this complexity class would imply the existence of pseudo-random number generators (-5[1])of hardness 2 to the n to the epsilon. A language is in this class if and only if it is Turing reducible to a sparse set. BPP is contained in this complexity class by Adleman’s theorem. All unary languages, even ones that are undecidable, are in this complexity class because you can “hardwire” a bit for each input length. A circuit complexity (15[1])approach to proving that P does not equal NP would attempt to show that NP is not in this class, which is the class of all languages with polynomial size circuits. For 15 points, name this non-uniform complexity class that contains problems solvable by a polynomial time Turing machine with access to polynomial advice. ■END■ (0[5])

Back to tossups