La madre de todos los NP-Complete es: Satisfacción
La teoría de la integridad de NP comenzó a partir de la satisfacción , que demostró ser NP-completa.
El teorema de Cook-Levin es un hito fundamental en la teoría de la integridad de NP.
Después de esto, se ha demostrado que muchos otros problemas son NP-Completos al mostrar, para un problema P, ( 3-SAT [matemáticas] <_ {P} [/ matemáticas] [matemáticas] Problema [/ matemáticas] [matemáticas ] P [/ matemática]) [matemática] \ wedge [/ matemática] ([matemática] P [/ matemática] [matemática] \ en [/ matemática] NP ).
Hay MUCHOS problemas NP-Complete, incluidos algunos problemas de gráficos:
i) Cubierta de vértice
ii) Establecer cubierta
iii) Problema de camarilla
……… Y la lista continúa (Verifique: 21 problemas NP-completos de Karp para probablemente los más importantes)
- Cómo ver si se está bloqueando la computadora
- ¿Cuáles son algunas señales de que uno es un prodigio de la informática?
- Cómo integrar el aprendizaje automático y la medicina como carrera y trabajar como investigador o pasante para Verily
- ¿Por qué la longitud de palabra de una computadora tiene el poder de 2?
- ¿Cuántas páginas (estándar de 8.5 "x11") se necesitarían para almacenar 100 TB de datos de texto sin formato?
Una vez hecho esto, se han comprobado muchos problemas de NP-Complete utilizando la transitividad de las reducciones de Poly-Time :
Suponga que [matemática] P_ {1} [/ matemática] [matemática] \ en [/ matemática] NP-Complete [matemática] \ implica [/ matemática] 3-SAT [matemática] <_ {P} [/ matemática] [matemática ] P_ {1} [/ matemáticas]
Si, [matemática] \ existe [/ matemática] [matemática] f [/ matemática]: [matemática] P_ {1} [/ matemática] [matemática] \ a [/ matemática] [matemática] P_ {2} [/ matemática ], [matemáticas] \ ni [/ matemáticas], ([matemáticas] f [/ matemáticas] = [matemáticas] Poli (| P_ {1} | [/ matemáticas])) [matemáticas] \ cuña [/ matemáticas] ([ matemática] P_ {2} [/ matemática] [matemática] \ en [/ matemática] NP )
[matemáticas] \ implica [/ matemáticas] 3-SAT [matemáticas] <_ {P} [/ matemáticas] [matemáticas] P_ {2} [/ matemáticas]
[matemáticas] \ implica [/ matemáticas] [matemáticas] P_ {2} [/ matemáticas] [matemáticas] \ en [/ matemáticas] NP-Complete
Entonces, aquí hay una lista de problemas NP-Complete: Lista de problemas NP-complete
Aquí está mi referencia para la Teoría de la aproximación de la dureza y la integridad de NP: computadoras e intratabilidad: una guía para la teoría de la integridad de NP (Serie de libros en las ciencias matemáticas): Michael R. Garey, David S. Johnson: 9780716710455 : Amazon.com: Libros
Nota : Aparentemente, a pesar de mostrar reducciones de 3-SAT , había escrito descuidadamente Satisfacción del circuito , al tiempo que me refería a la Satisfacción (la primera se reduce a la segunda). ¡Muchas gracias a Hans Hyttel por señalar el error!
