APX (Complexitat)

De Viquipèdia
Salta a la navegació Salta a la cerca

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.[1] 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[modifica]

APX està inclosa dins de la classe NPO i alhora conté a la classe PTAS.[2][3][4]

Referències[modifica]

  1. 1941-, Ausiello, G. (Giorgio),. Complexity and Approximation : Combinatorial Optimization Problems and Their Approximability Properties. Berlin, Heidelberg: Springer Berlin Heidelberg, 1999. ISBN 9783642584121. 
  2. «Complexity Zoo:N - Complexity Zoo». Arxivat de l'original el 2017-07-21. [Consulta: 10 desembre 2018].
  3. «Complexity Zoo:P - Complexity Zoo». Arxivat de l'original el 2018-01-19. [Consulta: 10 desembre 2018].
  4. V., Vazirani, Vijay. Approximation algorithms. Berlín: Springer, 2001. ISBN 3540653678.