Lo primero que debes tener es una idea básica sobre estos conceptos:
NP-Complete
NP-Complete es una clase de complejidad que representa el conjunto de todos los problemas X en NP para los cuales es posible reducir cualquier otro problema NP Y a X en tiempo polinómico.
- Si tengo los números n> 0, k> 0, a> 0 y el número primo x .. ¿Cuál es la forma más rápida de calcular ((n ^ k) * a) módulo x?
- ¿Cuáles son algunos problemas abiertos importantes o interesantes en la teoría de la codificación?
- ¿Qué libro debo usar para preguntas y soluciones para matemáticas discretas?
- ¿Podría un genio aleatorio resolver el problema P vs NP o pasará a través de avances muy lentos en la ciencia por un grupo de personas que trabajan juntas?
- ¿Puede un modelo de aprendizaje automático tener exactamente un 100% de especificidad?
Intuitivamente, esto significa que podemos resolver Y rápidamente si sabemos cómo resolver X rápidamente. Precisamente, Y es reducible a X , si hay un algoritmo de tiempo polinomial f para transformar instancias y de Y en instancias x = f(y) de X en tiempo polinomial, con la propiedad de que la respuesta a y es sí, si y solo si la respuesta a f(y) es sí.
Ejemplo
3-SAT . Este es el problema en el que se nos da una conjunción (AND) de disyunciones de 3 cláusulas (OR), declaraciones de la forma
(x_v11 O x_v21 O x_v31) Y
(x_v12 O x_v22 O x_v32) Y
… Y
(x_v1n O x_v2n O x_v3n)
donde cada x_vij es una variable booleana o la negación de una variable de una lista predefinida finita (x_1, x_2, ... x_n) .
Se puede demostrar que cada problema de NP puede reducirse a 3-SAT . La prueba de esto es técnica y requiere el uso de la definición técnica de NP ( basada en máquinas de Turing no deterministas ). Esto se conoce como el teorema de Cook .
Lo que hace que los problemas NP-completos sean importantes es que si se puede encontrar un algoritmo determinista de tiempo polinómico para resolver uno de ellos, cada problema NP puede resolverse en tiempo polinómico (un problema para gobernarlos todos).
NP-hard
Intuitivamente, estos son los problemas que son al menos tan difíciles como los problemas NP-completos . Tenga en cuenta que los problemas NP-hard no tienen que estar en NP , y no tienen que ser problemas de decisión .
La definición precisa aquí es que un problema X es NP-duro, si hay un problema NP completo Y , de modo que Y es reducible a X en tiempo polinomial .
Pero dado que cualquier problema NP-completo puede reducirse a cualquier otro problema NP-completo en tiempo polinómico, todos los problemas NP-completos pueden reducirse a cualquier problema NP-difícil en tiempo polinómico. Entonces, si hay una solución a un problema NP-duro en tiempo polinómico, hay una solución a todos los problemas NP en tiempo polinómico.
Ejemplo
El problema de detención es un problema NP-difícil. Este es el problema que da un programa P y entrada I , ¿se detendrá? Este es un problema de decisión pero no está en NP. Está claro que cualquier problema de NP completo se puede reducir a este. Como otro ejemplo, cualquier problema NP-complete es NP-hard.
Mi problema NP-complete favorito es el problema del Buscaminas.
P = NP
Este es el problema más famoso en informática y una de las preguntas pendientes más importantes en las ciencias matemáticas. De hecho, el Instituto Clay está ofreciendo un millón de dólares para una solución al problema (el informe de Stephen Cook en el sitio web de Clay es bastante bueno).
Está claro que P es un subconjunto de NP. La pregunta abierta es si los problemas de NP tienen o no soluciones deterministas de tiempo polinomial. Se cree en gran medida que no lo hacen. Aquí hay un artículo reciente sobresaliente sobre el último (y la importancia) del problema P = NP: El estado del problema P versus NP.
El mejor libro sobre el tema es Computadoras e Intractabilidad de Garey y Johnson.
Espero eso ayude….
