apx (773B)
1 # APX 2 3 class of [nptime] [optimization_problem] with [approximation] in polynomial time 4 with a ratio bounded by a constant 5 - analogue but for [counting_problem]? 6 7 Being in this class is weaker than existence of a [ptas], and if P neq NP then there are problems in [apx] that do not have a [ptas] 8 9 - [apx]-hard: as hard as problems that can be approximated within constant factor 10 - [log_apx]-hard: as hard as problems that can be approximated within a log factor 11 - [poly_apx]-hard: 12 - for instance [maximum_independent_set] 13 - on a [apx] subsetneq [log_apx] subsetneq [poly_apx] 14 - et ces inclusions sont strictes si P neq NP, reference [escoffier2007structures] 15 16 reference: [lee2021classifying] 17 18 [apx_counting] 19 20 See also: [approximation_algorithm] 21 22 Up: [complexity_class]