Supongo que está decentemente familiarizado con la noción básica de clases de complejidad.
Observa esta foto.
- Cómo aplicar mi enfoque para resolver el problema antes de abrir la solución
- ¿Cómo recomienda Foursquare las sugerencias de mis amigos de Facebook?
- ¿Qué estructuras de datos admiten la inserción, eliminación y selección de un elemento aleatorio con un límite de complejidad de tiempo [matemática] O (1) [/ matemática]?
- ¿Cuál es la diferencia entre un árbol AVL y un árbol de búsqueda binario?
- Cómo hacer que los algoritmos sean eficientes
Usted sabe que los problemas de NP son aquellos que no tienen una solución eficiente. Ahora, habrá una variación en la eficiencia algorítmica de las soluciones en los problemas bajo la clase NP, por lo que es muy probable que algunos problemas en NP sean más difíciles que sus contrapartes (en NP). Entonces, para distinguir tales problemas, la clase NP se divide en NP-Complete y NP-Hard. (Algunos problemas de NP podrían no estar en ninguna categoría).
Mira el círculo más grande. Eso es NP. Ahora imagine algunos problemas súper difíciles que son incluso más difíciles que los problemas más difíciles en NP. Esa es la parábola en la foto de arriba. Puede ver que no hay límite superior en los problemas NP-Hard, lo que claramente significa que hay muchos problemas para los que no hay una solución conocida, incluso en el Tiempo Recursivo. Esto aclara la noción sobre la clase de complejidad NP-Hard, que esencialmente contiene los problemas que son más difíciles que todos los problemas en NP.
Además, observará que hay una intersección significativa entre el círculo y la parábola, que es el área que contiene los problemas más difíciles de NP. Sí, los problemas que están certificados para estar en NP (su verificación es posible en tiempo lineal) pero son más difíciles que el resto de los problemas en NP. Forman una capa delgada del círculo que contiene todos los problemas de NP. Pero también están en NP-hard. ¿Cómo es eso? ¡Porque ellos también son más difíciles que los problemas más difíciles (los problemas en NP)!
Ahora puede que se pregunte cuál es la necesidad de separar NP-hard de NP y obtener una clase NP-Complete completamente nueva. Ciertamente, esto parece estar aumentando el desorden ya existente … Pero hay una trampa. Los problemas NP-Hard son especiales. ¡De una manera que una solución a los problemas NP-Hard daría una solución a todos los problemas en NP! .
Ya sabe que la mayoría de los problemas en NP-Hard no se pueden resolver. Entonces, ¿de qué sirve si ni siquiera sabemos cómo resolverlos? Ahí es donde entran los problemas de NP-Complete. Sabemos que su solución existe, aunque en un tiempo ineficiente. Pero se pueden resolver. Entonces, si de alguna manera, encontramos una solución de tiempo polinomial para cualquier problema en NP-Complete, significaría que todos y cada uno de los problemas en NP pueden resolverse en tiempo polinómico, de manera eficiente. Y eso probablemente terminará este punto muerto en P vs NP.
