computer science - polinomial - ¿cómo se demostró que los primeros problemas NP-completos eran NP-completos?
problemas np hard (2)
Para darle la esencia de la prueba (que es varias páginas difíciles en Computadoras e Intractibilidad de Garey & Johnson):
Cualquier problema computacional se puede expresar como una máquina de Turing.
Es posible expresar la máquina de Turing como un problema lógico, que satisface ciertas restricciones de complejidad.
Por lo tanto, si puede resolver el problema de lógica en tiempo polinomial, puede resolver el problema de la máquina de Turing en tiempo polinomial.
Esto (junto con algunas otras consideraciones) muestra que si puede resolver el problema de lógica en tiempo polinomial, puede resolver cualquier problema de NP en tiempo polinomial. Siendo esta la definición de NP-completo, el problema lógico es, por lo tanto, NP-completo, y puede usarse como base para otros problemas.
El problema lógico utilizado se llama Satisfabilidad (a menudo abreviado como SAT). Dada una serie de cláusulas de la forma (A o no-B o no-C) (cláusulas que consisten en cualquier número de proposiciones y negaciones de proposiciones conectadas por lógica o), ¿hay una asignación de valores de verdad a las proposiciones que hace que todo las cláusulas son verdad?
NP-integridad es una propiedad bien definida. La única razón por la que dudaría si un problema es que NP-complete es que pensó que podría reducir otro problema de NP-complete, pero aún no ha logrado encontrar un problema conveniente ni obtener una prueba.
La pregunta no es si existen problemas NP completos, o cómo demostrar que un problema es NP completo, sino qué significa eso. Nadie ha producido todavía un algoritmo de tiempo polinomial para resolver un problema NP-completo, y nadie ha demostrado que ese algoritmo no pueda existir. Independientemente de si P = NP, ciertamente no tenemos buenos algoritmos para resolver ningún problema NP-completo.
Este es uno de los Problemas del Milenio de la Fundación Claypool, así que si puedes encontrar una prueba que ha eludido a algunas personas muy brillantes durante algunos años, hay un millón de dólares para ti.
De la entrada de wikipedia en NP-Complete:
"La forma más fácil de probar que un nuevo problema es NP-complete es primero probar que está en NP, y luego reducir algún problema conocido de NP-complete".
Estoy bastante seguro de que entiendo esto: si tengo un problema, puedo demostrar que es NP-Completo si:
mostrar que está en NP (una solución al problema puede verificarse en tiempo polinomial en una máquina de Turing no determinista)
Demuestre que un problema ya conocido como NP-Complete puede ''reducirse'' al nuevo problema
Entonces, mi pregunta es, ¿cómo fueron ''probados'' los primeros problemas NP-completos para ser NP-completos? En un momento, el conjunto de problemas conocidos de NP-complete debe haber sido cero, y esto habría imposibilitado recurrir al paso 2 en el proceso anterior.
Esto me hace pensar que hay un método diferente para la prueba que no conozco. O eso, o tal vez toda la propiedad NP-completa se ''asume'' para ciertos problemas debido a la falta de una solución conocida de tiempo polinomial. (en realidad, después de haber escrito esto, no me sorprendería si este es el caso, pero me gustaría algún comentario del gurú de cualquier manera).
La clase NP puede definirse como la clase de problemas decidibles por una máquina de Turing no determinista en tiempo polinomial. Este teorema muestra que SAT es NP-completo codificando la operación de cualquier máquina de Turing no determinista mediante una fórmula booleana, de tal manera que la máquina acepta si y solo si esa fórmula es SATISFiable.
Históricamente hablando, la noción de NP-completitud fue introducida en el artículo seminal de Richard Karp ( Reducibility Among Combinatorial Problems ), donde definió NP-completeness, usó el teorema de Cook, y en una gran oportunidad, demostró 21 problemas NP-complete.