¿Cómo se puede demostrar que el SAT es NP-completo?

Question

Tal como es, ¿cómo probar que el SAT es NP-completo?

Yo sé lo que quiere decir con NP-completo, por lo que no necesito una explicación al respecto.

Lo que yo quiero saber es ¿cómo se sabe que uno de los problemas, tales como el SAT, es NP-completo sin tener que recurrir a la reducción de otros problemas como problema hamiltoniano o lo que sea.

Answer 1

Creo 3-SAT se redujo originalmente de la satisfacibilidad más general en el documento de Karp que esbozó problemas NP-completos 21 .

Wikipedia tiene una descripción de cómo para demostrar que satisfacibilidad es NP-completo, un resultado que es conocido como el teorema de Cook . La idea de esta prueba es demostrar que cualquier máquina de Turing no determinista tiempo polinómico se puede modelar como una expresión booleana con el tamaño polinomio. La expresión booleana tiene términos para representar el espacio de configuración válida de la máquina de Turing: donde la cabeza de la cinta es, lo que el estado actual es, qué símbolos se escriben en la cinta, y lo que las transiciones son válidos en cada posición. Debido a que el NTM se detendrá en tiempo polinómico, el espacio de configuración está limitada y podemos hacer una (gran) expresión polinómica para representarla.