Según parece, los problemas se determinan como NP-completos si se puede demostrar que son equivalentes a otro problema NP-completo. Sin embargo, me pregunto cómo se demostró que el problema NP-completo "original" era NP-completo. Si alguien pudiera decir cómo se hizo, se lo agradecería.
Respuesta
¿Demasiados anuncios?
Como ha señalado MJD, Garey y Johnson ofrecen una explicación muy amena de por qué el SAT es NP-completo. La idea básica es muy sencilla (y elegante), pero los detalles implican no poca complicación. He aquí una explicación reducida.
Problemas NP: Un problema de decisión $X$ está en NP si, por definición, existe alguna máquina de Turing no determinista $M$ de manera que cuando $M$ se le da una instancia, $I$ de $X$ como su entrada, puede decidir en tiempo polinomial en la longitud de $I$ si $I$ tiene una solución o no.
Problemas NP-Completos: Una decisión $Y$ un problema en NP se llama NP-completo si para cualquier problema $X\in$ NP, existe una transformación en tiempo polinómico $f$ que asigna una instancia $I$ de $X$ en una instancia $f(I)$ de $Y$ de tal manera que $I$ tiene una solución si y sólo si $f(I)$ tiene una solución. Parece como si mostrar que $Y$ es NP-completo debería ser realmente intimidante: ¿cómo podríamos establecer que cada El problema NP puede ser transformado en poli-tiempo a nuestro $Y$ ?
SAT, un problema especial de NP: Recordemos que el problema de decisión SAT está formado por instancias $I$ que son expresiones booleanas sobre un conjunto $V$ de las variables booleanas. No es demasiado difícil demostrar que existe una TM no determinista $M$ que, cuando se le da una instancia $I$ puede determinar, en tiempo polinómico en la longitud de $I$ si hay una asignación de valores a $V$ que hará que $I$ verdadero o si no hay tal asignación (esencialmente, sólo generar de forma no determinista todas las posibles asignaciones y probar cada una de ellas para la satisfacción).
SAT es NP-completo: Aquí viene la parte inteligente. Si queremos demostrar que SAT es NP-completo, tenemos que ser capaces de transformar cualquier Problema NP, $X$ a SAT. Hay cientos de problemas NP, de formas muy variadas; ¿cómo podríamos transformar cada uno de ellos en instancias de SAT? Bueno, lo único que tienen en común todos los problemas NP es que pueden ser decididos por TMs, así que nos basamos en esa propiedad. Para cualquier problema NP $X$ expresamos su decisor TM, $M_X$ por una enorme expresión booleana $B$ de tal manera que para una instancia $I$ de $X$ , $M_X(I)$ responderá "sí" si y sólo si $B$ puede ser satisfecha. En esencia, estamos modelando la acción de la TM $M_X$ en $I$ . Una vez que lo hagamos y demostremos que la transformación puede realizarse en tiempo polinómico, habremos demostrado que SAT es efectivamente NP-completo.
Todo el trabajo importante está en los detalles: por ejemplo, necesitamos una expresión booleana que represente " $M_X$ sólo puede estar en un estado a la vez", otro que dice "desde esta configuración, $M_X$ sólo puede hacer un movimiento a estas otras configuraciones" y así sucesivamente. (Una vez hice esto para una MT de un solo movimiento; requería 16 variables y 38 subcláusulas unidas. Uf, pero la cuestión es que puede siempre se hace).
