APX (Complexitat)
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
APX està inclosa dins de la classe NPO i alhora conté a la classe PTAS.[2][3][4]
Referències
- ↑ 1941-, Ausiello, G. (Giorgio),. Complexity and Approximation : Combinatorial Optimization Problems and Their Approximability Properties. Berlin, Heidelberg: Springer Berlin Heidelberg, 1999. ISBN 9783642584121.
- ↑ «Complexity Zoo:N - Complexity Zoo». Arxivat de l'original el 2017-07-21. [Consulta: 10 desembre 2018].
- ↑ «Complexity Zoo:P - Complexity Zoo». Arxivat de l'original el 2018-01-19. [Consulta: 10 desembre 2018].
- ↑ V., Vazirani, Vijay. Approximation algorithms. Berlín: Springer, 2001. ISBN 3540653678.
Classes de complexitat | |
|---|---|
| Considerades tractables | DLOGTIME · AC0 · ACC0 · TC0 · L · SL · RL · NL · NC · SC · CC · P · P-complet · ZPP · RP · BPP · BQP · APX |
| Suposadament intractables | UP · NP · NP-complet · NP-hard · co-NP · co-NP-complet · AM · QMA · PH · ⊕P · PP · ♯P · ♯P-complet · IP · PSPACE · PSPACE-complet |
| Considerades intractables | EXPTIME · NEXPTIME · EXPSPACE · ELEMENTARY · PR · R · RE · ALL |
| Jerarquia de classes | |
| Families de classes | DTIME · NTIME · DSPACE · NSPACE · Demostració provable per probabilitat · Sistema de demostració interactiu |
