Dureza de aproximación

En informática , la dificultad de aproximación es un campo que estudia la complejidad algorítmica de encontrar soluciones casi óptimas a problemas de optimización .

La dificultad de la 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 aproximarse eficientemente. Típicamente, dichos 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 en tiempo polinomial para el problema es imposible a menos que NP=P . Sin embargo, algunos resultados de la dificultad de la aproximación se basan en otras hipótesis, entre las cuales destaca 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, Teofilo F. Gonzalez y Sartaj Sahni comenzaron el estudio de la dificultad de la aproximación, al demostrar que ciertos problemas de optimización eran NP-difíciles incluso para aproximarlos dentro de una razón de aproximación dada . Es decir, para estos problemas, hay 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 dificultad de la aproximación se ocupa del estudio del umbral de aproximación de este tipo de problemas.

Para ver un ejemplo de un problema de optimización NP-difícil que es difícil de aproximar, consulte cobertura de conjuntos y cobertura de vértices .

• Teorema PCP

• Trevisan, Luca (27 de julio de 2004), Inaproximabilidad de problemas de optimización combinatoria (PDF) , arXiv : cs/0409043 , Bibcode : 2004cs........9043T

• CSE 533: El teorema PCP y la dificultad de la aproximación, otoño de 2005 , programa de estudios de la Universidad de Washington , Venkatesan Guruswami y Ryan O'Donnell