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 cuales su solución puede aproximarse eficientemente. Normalmente, estos límites muestran un factor de aproximación más allá del cual un problema se vuelve NP-difícil , lo que implica que encontrar una aproximación de tiempo polinomial para el problema es imposible a menos que NP=P . Sin embargo, cierta dureza de los resultados de aproximación se basa en otras hipótesis, una de las cuales es la conjetura del juego único .
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 punto. En la década de 1970, Teófilo F. González y Sartaj Sahni comenzaron el estudio de la dureza de aproximación, demostrando que ciertos problemas de optimización eran NP-difíciles incluso de aproximarse dentro de una relación de aproximación determinada . Es decir, para estos problemas, existe un umbral tal que cualquier aproximación en tiempo polinomial con una relación de aproximación más allá de este umbral podría usarse para resolver problemas NP-completos en tiempo polinómico. [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 relación de aproximación posible.
La teoría de la dureza de la 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 set cover .