Hemos estado escribiendo sobre algoritmos eficientes para resolver problemas complejos, como el camino más corto, el gráfico de Euler, el árbol de expansión mínimo, etc. Todas esas fueron historias de éxito de diseñadores de algoritmos. En este post, se discuten historias de fracasos de la informática.
¿Todos los problemas computacionales pueden ser resueltos por una computadora? Hay problemas computacionales que no se pueden resolver con algoritmos, incluso con tiempo ilimitado. Por ejemplo, problema de parada de Turing (Dado un programa y una entrada, si el programa eventualmente se detendrá cuando se ejecute con esa entrada, o se ejecutará para siempre). Alan Turing demostró que el algoritmo general para resolver el problema de detención para todos los pares de entrada de programa posibles no puede existir. Una parte clave de la prueba es que la máquina de Turing se usó como una definición matemática de una computadora y un programa (Problema de Detención de la fuente).
El estado de los problemas completos de NP es otra historia de fallos, los problemas completos de NP son problemas cuyo estado es desconocido. Aún no se ha descubierto ningún algoritmo de tiempo polinómico para ningún problema completo de NP, ni nadie ha podido probar que no exista ningún algoritmo de tiempo polinómico para ninguno de ellos. La parte interesante es, si cualquiera de los problemas completos de NP se puede resolver en tiempo polinómico, entonces todos ellos se pueden resolver.
¿Cuáles son los problemas NP, P, NP-completo y NP-Duro?
P es un conjunto de problemas que pueden ser resueltos por una máquina de Turing determinista en tiempo polinómico.
NP es un conjunto de problemas de decisión que pueden ser resueltos por una Máquina de Turing No determinista en tiempo polinómico. P es un subconjunto de NP (cualquier problema que pueda ser resuelto por una máquina determinista en tiempo polinómico también puede ser resuelto por una máquina no determinista en tiempo polinómico).Informalmente, NP es un conjunto de problemas de decisión que se pueden resolver mediante un tiempo polinómico a través de un» Algoritmo de la Suerte», un algoritmo mágico que siempre adivina correctamente entre el conjunto de opciones dado (Referencia de Fuente 1).
NP-los problemas completos son los problemas más difíciles en el conjunto NP. Un problema de decisión L es NP-completo si:
1) L está en NP (Cualquier solución dada para problemas NP-completos se puede verificar rápidamente, pero no hay una solución conocida eficiente).
2) Cada problema en NP es reducible a L en tiempo polinómico (La reducción se define a continuación).
Un problema es NP-Hard si sigue la propiedad 2 mencionada anteriormente, no necesita seguir la propiedad 1. Por lo tanto, el conjunto completo NP es también un subconjunto del conjunto duro NP.
Problemas de decisión vs Optimización
NP-la integridad se aplica al ámbito de los problemas de decisión. Se configuró de esta manera porque es más fácil comparar la dificultad de los problemas de decisión que la de los problemas de optimización. En realidad, sin embargo, poder resolver un problema de decisión en tiempo polinómico a menudo nos permitirá resolver el problema de optimización correspondiente en tiempo polinómico (utilizando un número polinómico de llamadas al problema de decisión). Por lo tanto, discutir la dificultad de los problemas de decisión a menudo equivale a discutir la dificultad de los problemas de optimización. (Fuente Ref 2).
Por ejemplo, considere el problema de la cubierta de vértices (Dado un gráfico, averigüe el conjunto de vértices de tamaño mínimo que cubre todas las aristas). Es un problema de optimización. El problema de decisión correspondiente es, dado el gráfico no dirigido G y k, ¿hay una cubierta de vértice de tamaño k?
¿Qué es la Reducción?Deje que L1 y L2 sean dos problemas de decisión. Supongamos que el algoritmo A2 resuelve L2. Es decir, si y es una entrada para L2, el algoritmo A2 responderá Sí o No, dependiendo de si y pertenece a L2 o no.La idea es encontrar una transformación de L1 a L2 para que el algoritmo A2 pueda ser parte de un algoritmo A1 para resolver L1.La reducción del aprendizaje en general es muy importante. Por ejemplo, si tenemos funciones de biblioteca para resolver cierto problema y si podemos reducir un nuevo problema a uno de los problemas resueltos, ahorramos mucho tiempo. Consideremos el ejemplo de un problema en el que tenemos que encontrar una ruta de producto mínima en un gráfico dirigido dado, donde el producto de la ruta es la multiplicación de pesos de bordes a lo largo de la ruta. Si tenemos código para que el algoritmo de Dijkstra encuentre la ruta más corta, podemos tomar un registro de todos los pesos y usar el algoritmo de Dijkstra para encontrar la ruta mínima del producto en lugar de escribir un código nuevo para este nuevo problema.
¿Cómo probar que un problema dado es NP completo?
De la definición de NP-completo, parece imposible probar que un problema L es NP-Completo. Por definición, nos obliga a demostrar que cada problema en NP es tiempo polinómico reducible a L. Afortunadamente, hay una forma alternativa de probarlo. La idea es tomar un problema conocido de NP Completo y reducirlo a L. Si la reducción del tiempo polinómico es posible, podemos probar que L es NP-Completo por transitividad de reducción (Si un problema NP-Completo es reducible a L en tiempo polinómico, entonces todos los problemas son reducibles a L en tiempo polinómico).
¿Cuál fue el primer problema probado como NP-Completo?Debe haber algún primer problema NP-Completo probado por definición de problemas NP-Completos. SAT (problema de satisfabilidad booleana) es el primer problema NP-Completo probado por Cook (Consulte el libro CLRS para ver la prueba).
Siempre es útil conocer la integridad de NP, incluso para ingenieros. Supongamos que se le pide que escriba un algoritmo eficiente para resolver un problema extremadamente importante para su empresa. Después de pensar mucho, solo se puede llegar a un enfoque de tiempo exponencial que no es práctico. Si no sabes acerca de NP-Completitud, solo puedes decir que no podría venir con un algoritmo eficiente. Si conoce la NP-Completitud y demuestra que el problema es NP-completo, puede decir con orgullo que es poco probable que exista la solución de tiempo polinómico. Si hay una solución de tiempo polinómico posible, entonces esa solución resuelve un gran problema de la informática que muchos científicos han estado intentando durante años.
Pronto discutiremos más problemas de NP-Completo y sus pruebas de NP-Completo.