classe de complexitat From Wikipedia, the free encyclopedia
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.
APX està inclosa dins de la classe NPO i alhora conté a la classe PTAS.[2][3][4]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.