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 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. (-5[1])A circuit complexity 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. (-5[1])For (-5[1])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[4])

Back to tossups

Buzzes

Summary