¿Cómo se demostró que los primeros problemas de NP completo son NP completos?

Question

De la entrada de Wikipedia en NP-Complete:

" La forma más fácil de demostrar que algún problema nuevo es NP-complete es primero demostrar 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-Complete si:

1. muestra que está en NP (una solución para el problema se puede verificar en tiempo polinómico en un máquina de Turing no determinista)

2. Demuestre que un problema que ya se conoce como NP-Complete puede ser 'reducido' al nuevo problema

Entonces, mi pregunta es, ¿cómo se 'probó' que los primeros problemas NP-completos fueran NP-completos? En un momento, el conjunto de problemas conocidos de NP completo debe haber sido cero, y esto habría hecho imposible recurrir al paso 2 en el proceso anterior.

Esto me hace pensar que hay un método diferente para la prueba del que no estoy al tanto. O eso, o tal vez toda la propiedad NP-completa se 'asume' para ciertos problemas debido a la falta de una solución de tiempo polinomial conocida. (en realidad, después de escribir esto, no me sorprendería si este fuera el caso, pero me gustaría recibir comentarios de los gurús de cualquier manera).

Answer 1

Teorema de Cook

La clase NP se puede definir como la clase de problemas que una máquina de Turing no determinista puede resolver en tiempo polinómico. Este teorema muestra que SAT es NP-completo al codificar el funcionamiento de cualquier máquina de Turing no determinista mediante una fórmula booleana, de tal manera que la máquina acepte si y solo si esa fórmula es SATisfiable.

Históricamente hablando, la noción de integridad de NP se introdujo en el artículo seminal de Richard Karp ( Reducibilidad entre problemas combinatorios ), donde definió la completitud de NP, usó el teorema de Cook y, en una gran oportunidad, demostró 21 problemas de NP completo.

Answer 2

Para darle la esencia de la prueba (que son varias páginas de trabajo duro en de Garey & amp; Johnson):

Cualquier problema computacional puede expresarse como una máquina de Turing.

Es posible expresar la máquina de Turing como un problema lógico, satisfaciendo ciertas restricciones de complejidad.

Por lo tanto, si puede resolver el problema lógico en tiempo polinómico, puede resolver el problema de la máquina de Turing en tiempo polinómico.

Esto (junto con algunas otras consideraciones) muestra que si puede resolver el problema lógico en tiempo polinómico, puede resolver cualquier problema NP en tiempo polinómico. Siendo esta la definición de NP completo, el problema lógico es 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ógico o), ¿hay una asignación de valores de verdad a las proposiciones que hace que todos las cláusulas verdaderas?

NP-completeness es una propiedad bien definida. La única razón por la que tendría dudas sobre un problema de NP-complete es porque pensó que podría reducir otro problema de NP-complete, pero aún no ha logrado encontrar un problema conveniente o obtener una prueba.

La pregunta no es si existen problemas con NP completo o cómo demostrar que un problema es NP completo, sino qué significa eso. Nadie ha producido aún un algoritmo de tiempo polinómico para resolver un problema de NP completo, y nadie ha demostrado que dicho algoritmo no pueda existir. Sea o no P = NP, ciertamente no tenemos buenos algoritmos para resolver ningún problema de NP completo.

Este es uno de los problemas del Milenio de la Fundación Claypool, por lo que si puede encontrar una prueba que haya eludido a algunas personas muy brillantes durante bastantes años, hay un millón de dólares para usted.