¿cómo se demostró que NP-complete era el primer NP-complete?

Question

partir de la entrada de Wikipedia sobre NP-Completo:

"La forma más fácil de probar que algún nuevo problema es NP-completo es el primero en demostrar que está en NP, y luego a reducir algo conocido problema NP-completo a que"

estoy bastante seguro de que entiendo esto: Si tengo un problema, puedo demostrar que es NP-completo si:

1. mostrar que está en NP (una solución a el problema se puede verificar en tiempo polinomial en un no máquina de Turing -deterministic)

2. Mostrar que un problema ya se sabe que es NP-completo puede 'reduce' al nuevo problema

Por lo tanto, mi pregunta es, ¿cómo fueron los primeros NP ¿Completa los problemas 'probados' para ser NP completo? 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).

Answer 1

Cook's Theorem

La clase NP se puede definir como la clase de problemas decidibles por una máquina de Turing no determinista en tiempo polinómico. Este teorema muestra que SAT es NP-completo codificando el funcionamiento 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 se introdujo en el artículo de Richard Karp seminal (Reducibility Among Combinatorial Problems), donde se define NP-completitud, se utiliza el teorema de Cook, y en un pez gordo, probado 21 problemas NP-completo.

Answer 2

para darle la esencia de la prueba (que es varias páginas de fuerza que van en Garey & de Johnson Computadoras y Intractibility):

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 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-completeness 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, pero qué significa eso. Nadie ha producido aún 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, por lo que si se puede llegar a una prueba de que ha estado eludiendo algunas personas muy brillantes durante bastantes años, hay un millón de dólares en él para usted.