Ungefärlig hårdhet
Inom datavetenskap är hårdhet av approximation ett område som studerar den algoritmiska komplexiteten för att hitta nära optimala lösningar på optimeringsproblem .
Omfattning
Approximationshårdhet kompletterar studiet av approximationsalgoritmer genom att bevisa, för vissa problem, en gräns för de faktorer med vilka deras lösning effektivt kan approximeras. Typiskt visar sådana gränser en approximationsfaktor bortom vilken ett problem blir NP-hårt , vilket antyder att det är omöjligt att hitta en polynomtidsapproximation för problemet om inte NP=P . Viss hårdhet av approximationsresultat är dock baserade på andra hypoteser, en anmärkningsvärd bland dem är den unika spelförmodan .
Historia
Sedan början av 1970-talet var det känt att många optimeringsproblem inte kunde lösas i polynomtid om inte P = NP , men i många av dessa problem kunde den optimala lösningen effektivt approximeras till en viss grad. På 1970-talet Teofilo F. Gonzalez och Sartaj Sahni studien av approximationshårdhet, genom att visa att vissa optimeringsproblem var NP-svåra till och med att approximera inom ett givet approximationsförhållande . Det vill säga, för dessa problem finns det ett tröskelvärde så att varje approximation av polynomtid med approximationsförhållande över detta tröskelvärde skulle kunna användas för att lösa NP-fullständiga problem i polynomtid. I början av 1990-talet, med utvecklingen av PCP- teorin, blev det klart att många fler approximationsproblem var svåra att approximera, och att (om inte P = NP) många kända approximationsalgoritmer uppnådde bästa möjliga approximationsförhållande.
Hardness of approximation theory handlar om att studera approximationströskeln för sådana problem.
Exempel
För ett exempel på ett NP-hårt optimeringsproblem som är svårt att uppskatta, se uppsättningsomslag .
Se även
Vidare läsning
- Trevisan, Luca (27 juli 2004), Inapproximability of Combinatorial Optimization Problems (PDF)
externa länkar
- CSE 533: PCP Theorem and Hardness of Approximation, hösten 2005, kursplan från University of Washington , Venkatesan Guruswami och Ryan O'Donnell