En informática , la dureza de aproximación es un campo que estudia la complejidad algorítmica de encontrar soluciones casi óptimas a problemas de optimización .
La dureza de aproximación complementa el estudio de los algoritmos de aproximación al demostrar, para ciertos problemas, un límite en los factores con los que su solución puede ser aproximada eficientemente. Típicamente tales límites muestran un factor de aproximación más allá del cual un problema se vuelve NP-duro , lo que implica que encontrar una aproximación de tiempo polinomial para el problema es imposible a menos que NP=P . Sin embargo, algunos resultados de dureza de aproximación se basan en otras hipótesis, una notable entre las cuales es la conjetura de los juegos únicos .
Desde principios de la década de 1970 se sabía que muchos problemas de optimización no podían resolverse en tiempo polinomial a menos que P = NP , pero en muchos de estos problemas la solución óptima podía aproximarse eficientemente hasta cierto grado. En la década de 1970, Teófilo F. González y Sartaj Sahni comenzaron el estudio de la dureza de la aproximación, al mostrar que ciertos problemas de optimización eran NP-difíciles incluso para aproximarse dentro de una razón de aproximación dada . Es decir, para estos problemas, existe un umbral tal que cualquier aproximación en tiempo polinomial con una razón de aproximación más allá de este umbral podría usarse para resolver problemas NP-completos en tiempo polinomial. [1] A principios de la década de 1990, con el desarrollo de la teoría PCP , quedó claro que muchos más problemas de aproximación eran difíciles de aproximar y que (a menos que P = NP) muchos algoritmos de aproximación conocidos lograban la mejor razón de aproximación posible.
La teoría de la dureza de aproximación se ocupa del estudio del umbral de aproximación de tales problemas.
Para ver un ejemplo de un problema de optimización NP-hard que es difícil de aproximar, consulte la portada del conjunto .