¿Qué son los problemas NP-completos? ¿Cómo podemos resolverlos?

Un tipo de problema es “NP-complete” si está “en NP” y “NP-hard”.

Un tipo de problema (por ejemplo, el sudoku del juego) está “en NP” si, cuando propone una solución particular a una instancia particular del problema (por ejemplo, una cuadrícula de sudoku con todos los números completados), puedo verificar si es, de hecho, una solución (ha satisfecho todas las restricciones de sudoku) en tiempo polinómico. NP significa “polinomio no determinista”: si se me permitiera probar todas las soluciones posibles a la vez, o elegir mágicamente la solución correcta e intentarlo, podría resolver el problema en tiempo polinomial.

El tiempo polinómico significa que a medida que aumenta el tamaño del problema (por ejemplo, pasa de 9 × 9 sudoku a 16 × 16), la cantidad de trabajo que tengo que hacer también crece como un polinomio en el tamaño del problema. Cuando compruebo las soluciones de sudoku, para cada pequeño cuadrado, miro cada número en su fila, columna y cuadro para asegurarme de que no sean iguales. En general, hago 3 * n ^ 3 verificaciones, donde n es el número de cuadrados en una fila / columna / cuadro. 3 * n ^ 3 es un polinomio, por lo que mi algoritmo de comprobación de sudoku se ejecuta en tiempo polinómico. (Tal vez podría ser muy inteligente y evitar algunas verificaciones dobles para reducir un poco el polinomio. No es el punto).

Algunos problemas en NP también están en P, lo que significa que puede resolverlos en tiempo polinómico. Se cree ampliamente, pero no está comprobado, que hay problemas en NP que son demasiado difíciles de resolver en tiempo polinómico (el mejor algoritmo requiere una cantidad de tiempo que es exponencial en el tamaño del problema). Sudoku es un ejemplo de un problema que actualmente carece de una solución de tiempo polinomial.

Un tipo de problema es “NP-hard” si cada problema en NP puede reducirse a un problema de este tipo en tiempo polinómico. “Reducido” aquí significa “reformulado de tal manera que una solución para el segundo le permita encontrar una solución para el primero en tiempo polinómico”. El problema de 3-SAT (http://en.m.wikipedia.org/wiki/B…) es NP-hard, y de hecho puedo reducir sudoku (que está en NP) a 3-SAT codificando las restricciones de sudoku en lógica booleana (el cuadrado 1,1 es un 3 xo el cuadrado 1,2 es un 3 xor …).

Sudoku es NP-complete y, por lo tanto, NP-hard, por lo que una forma de resolver cualquier problema de NP-complete es reducirlo a un sudoku y luego resolverlo y traducirlo de nuevo. Dependiendo del tamaño del problema original, el sudoku resultante podría ser bastante grande, sin embargo :). Más en serio, probar todas las soluciones posibles y verificarlas siempre es una opción, y muchos problemas particulares de NP completo tienen algoritmos de aproximación que acercan algo a una solución más rápidamente que el enfoque de fuerza bruta.

R. Supongo que sabe qué clase de problemas de NP son, los problemas de NP completos son aquellos:
1. Pertenecen a la clase NP
2. Todo problema NP-completo se puede transformar en otro problema NP-completo en tiempo polinómico.
Ejemplo: 3SAT, cubierta de vértice, conjunto independiente, k-Clique.
NP-hard es una subclase de NP pero no forma parte de NP-complete.
La mayoría de los problemas de la clase NP se basan en decisiones, lo que significa que estamos buscando “¿Existe una solución”, no nos preocupa “Cuál es la solución”.
La propiedad especial de NP-complete es: por el punto 2 anterior: si encontramos una solución polinómica para un problema de NP-complete, entonces encontramos solución para todos ellos.
B. Se resuelven como problemas de decisión, luego intentamos la huerística o aproximaciones para obtener una solución adecuada. Pero todavía no existe un algoritmo que pueda calcular una solución en tiempo polinómico. Se han encontrado soluciones que funcionan en tiempo exponencial. Dependiendo del problema, existen diferentes métodos para resolverlos.

Consejo: las transformaciones NP-completas nos dicen que todos los problemas son igualmente difíciles. Los problemas NP-hard no se pueden transformar en NP-complete porque uno no puede transformar el problema difícil en uno fácil, pero viceversa es posible. Si se encuentra que un problema de NP-hard es NP-complete, significa que se ha encontrado la transformación del problema, no implica que todos los problemas de NP-hard puedan transformarse, NP-hard, NP-complete se establecen / clase de problemas, como es P.

¡Fuerza bruta!