P/poly - EMACS at CO - Buzzpoints App

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])

ANSWER: P/poly (“P slash poly”) [reject “P”]

<AW>

= Average correct buzz position

Conv. %	Power %	Average Buzz
0%	0%

Back to tossups

Buzzes

Player	Team	Opponent	Buzz Position	Value
Eric Bobrow	Dianetics for Diabetics	Edwardian Manifestation of All Colonial Sins	83	-5
Kevin Wang	a neural-net processor; a thinking machine	playing emacs while my parents are arguing	117	-5
Kevin Ye	We Bought a Complexity Zoo Story	screaming into the public static void main(String[] args)	118	-5
Dylan Minarik	Edwardian Manifestation of All Colonial Sins	Dianetics for Diabetics	141	0
Earthflax Geologybuzzer	Macro Editors	Eight Megabytes And Constantly Swapping	141	0
Ashvin Srivatsa	Eight Megabytes And Constantly Swapping	Macro Editors	141	0
Henry Cafaro	screaming into the public static void main(String[] args)	We Bought a Complexity Zoo Story	141	0