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).
- ¿Cómo dirigen los sistemas de guía del vehículo de lanzamiento la carga útil hacia órbitas tan precisas?
- ¿Puedo aprender algoritmos en mis vacaciones de verano si doy 8-10 horas cada día?
- ¿Desglosar el problema en piezas más pequeñas siempre ofrece una mejor solución?
- ¿Cuál es el algoritmo de aprendizaje automático requerido para el asistente virtual?
- ¿Cuál es la forma más fácil de animar el algoritmo de Dijkstra para Power Point Presentation?
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.
