En teoria de la complexitat, la classe de complexitat APX és el conjunt dels problemes d'optimització a NP que tenen algorismes aproximats de temps polinòmic fitats per un factor d'aproximació que és una constat. En termes senzills, els problemes dins d'aquesta classe tenen algorismes prou eficients que donen una resposta amb un factor constant respecte a la solució òptima.
Un algorisme aproximat s'anomena algorisme aproximat-f(n) per una entrada de mida n si es pot provar que la solució que troba aquest algorisme és almenys un factor f(n) pitjor que la solució òptima. A f(n) se'l denomina factor d'aproximació. Els problemes dins de la classe APX son aquells que la f(x) és una constant.
Relació amb d'altres classes APX està inclosa dins de la classe NPO i alhora conté a la classe PTAS.
Referències
Categoria:Classes de complexitat