complexity_class (694B)
1 # Complexity class 2 3 ## Classes 4 5 - [complexity_space] 6 - [nlogspace] 7 - [logspace] 8 - [complexity_time]: [complexity_time_classes] 9 - [spanl] 10 11 ## [complexity_hierarchy] 12 13 - [boolean_hierarchy] 14 - [polynomial_hierarchy] 15 16 ## Variants 17 18 - [counting_complexity] 19 - [sharpp] 20 - [approximation_class] 21 - [complexity_random] 22 - [advice] 23 - [p_poly] P/poly 24 - [l_poly] L/poly 25 - [optimization_problem] 26 - [NPO] 27 28 ## Results 29 30 - [time_hierarchy_theorem] / [space_hierarchy_theorem] 31 - https://mathoverflow.net/questions/40770/how-do-we-know-that-p-linspace-without-knowing-if-one-is-a-subset-of-the-othe/40771#40771 32 - P is different from SPACE(n) 33 34 Up: [computational_complexity] 35 36 Aliases: complexity classes