complexity_class (961B)
1 # Complexity class 2 3 ## Classes 4 5 - [complexity_space] 6 - [nlogspace] 7 - [logspace] 8 - [complexity_time] 9 - [ptime] / [p_complete] 10 - [linear_time], [linear_time_nearly], [linear_time_almost] 11 - [np_intermediate], cf [ladners_theorem] 12 - [nptime] 13 - [conptime] 14 - [np_cap_conp] 15 - [exptime] 16 - [nexptime] 17 - [spanl] 18 - [pp] 19 - [pspace] 20 - [pspace_complete] 21 - [oplusp] oplusP 22 - [us] US 23 24 ## [complexity_hierarchy] 25 26 - [boolean_hierarchy] 27 - [polynomial_hierarchy] 28 29 ## Variants 30 31 - [counting_complexity] 32 - [sharpp] 33 - [approximation_class] 34 - [complexity_random] 35 - [advice] 36 - [p_poly] P/poly 37 - [l_poly] L/poly 38 - [optimization_problem] 39 - [NPO] 40 41 ## Results 42 43 - [time_hierarchy_theorem] / [space_hierarchy_theorem] 44 - https://mathoverflow.net/questions/40770/how-do-we-know-that-p-linspace-without-knowing-if-one-is-a-subset-of-the-othe/40771#40771 45 - P is different from SPACE(n) 46 47 Up: [computational_complexity] 48 49 Aliases: complexity classes