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