Tamaño de letra
Tema
Ancho de lectura
Tipografía

Apuntes · Capítulo 13Complejidad

NP-completitud, demostrada

NP-completitud, demostrada

La semana pasada definimos NP sobre máquinas de Turing, de dos maneras que resultaron ser la misma: los lenguajes que tienen un verificador de tiempo polinomial, y los que decide una máquina no determinista de tiempo polinomial. Quedó planteada la pregunta de si P=NP\mathsf{P} = \mathsf{NP}, ahora con una definición precisa de cada lado.

En Análisis y Diseño de Algoritmos usaron esa pregunta sin poder tocar el fondo. Aprendieron a reducir un problema a otro, redujeron 3-SAT a conjunto independiente, a 3-coloreo y a suma de subconjuntos, y concluyeron que todos son NP-completos. Pero toda esa cadena colgaba de un teorema que solo se enunció: SAT es NP-completo. Sin él, las reducciones dicen que esos problemas son tan difíciles como SAT, y nada dice que SAT sea difícil.

Esta semana se demuestra. La demostración no se parece a las reducciones que ya conocen, porque no parte de un problema: parte de todos los problemas de NP a la vez. Lo único que tienen en común es que cada uno tiene una máquina no determinista de tiempo polinomial, y de eso sale la fórmula. La ejecución completa de la máquina se escribe en una tabla, el tableau, y la fórmula dice, celda por celda, que la tabla es una ejecución que acepta.

Es una demostración por construcción, y la vamos a ejecutar: un programa recibe una máquina, una entrada y el tamaño de la tabla, escribe la fórmula, minisat la resuelve y de la asignación sale la ejecución de la máquina. En la segunda sesión se completa el cuadro: de SAT a 3-SAT, una reducción nueva con gadgets, el borde entre 2-SAT y 3-SAT, la clase coNP y qué significaría que P fuera igual a NP.

Ruta de lectura.

Antes de clase (15–20 minutos): la introducción, Lo que ya saben: reducciones y NP-completitud y El primer problema NP-completo. Antes de la sesión B, De la fórmula del tableau a una fórmula en CNF. Con eso llegan sabiendo qué hay que demostrar y por qué no alcanza con una reducción de las de siempre.

En clase: Sesión A, de Una máquina de ejemplo a La reducción, ejecutada. Sesión B, de De la fórmula del tableau a una fórmula en CNF a Los solucionadores SAT en la práctica.

Después de clase: el Resumen y los Ejercicios, para repasar. Antes del laboratorio, Ventanas legales otra vez y El código de la semana. Para ampliar, las lecturas de apoyo del recuadro siguiente.

Lectura. Sipser, sec. 7.4 (NP-completeness) y 7.5 (Additional NP-complete Problems). Barak, capítulos 14 (Polynomial-time reductions), 15 (NP, NP completeness, and the Cook-Levin Theorem) y 16 (What if P equals NP?). Son apoyo: estos apuntes se pueden estudiar solos.

Código. Los programas de este capítulo están en code/week-13. Dentro del entorno del curso, entren a esa carpeta y corran make para compilar los ejemplos y make test para comprobarlos. Los comandos de este capítulo se corren desde ahí. El laboratorio está en lab/cook_levin.

Lo que ya saben: reducciones y NP-completitud

Una página de repaso, con la notación de este curso. Las reducciones de la semana 10 pedían que la función fuera computable. Ahora además tiene que ser rápida.

Definición. Un lenguaje AA se reduce en tiempo polinomial (polynomial-time reduction) a un lenguaje BB, y se escribe A≤pBA \leq_p B, si existe una función ff, computable por una máquina de Turing determinista de tiempo polinomial, tal que para toda cadena ww:

w∈A  ⟺  f(w)∈Bw \in A \iff f(w) \in B

La función traduce preguntas sobre AA en preguntas sobre BB sin cambiar la respuesta. Tres hechos, que en Algoritmos usaron todo el tiempo:

  • Si A≤pBA \leq_p B y B∈PB \in \mathsf{P}, entonces A∈PA \in \mathsf{P}. Para decidir si w∈Aw \in A se calcula f(w)f(w) y se le pregunta al algoritmo de BB. Como ff tarda un tiempo polinomial, ∣f(w)∣|f(w)| es polinomial en ∣w∣|w|, y un polinomio de un polinomio es un polinomio.
  • Leído al revés: si A≤pBA \leq_p B y A∉PA \notin \mathsf{P}, entonces B∉PB \notin \mathsf{P}. Es la forma en que se usa para mostrar dificultad: BB es al menos tan difícil como AA.
  • Es transitiva: si A≤pBA \leq_p B y B≤pCB \leq_p C, entonces A≤pCA \leq_p C, componiendo las dos funciones.

Definición. Un lenguaje BB es NP-difícil si todo lenguaje A∈NPA \in \mathsf{NP} cumple A≤pBA \leq_p B. Es NP-completo si es NP-difícil y además B∈NPB \in \mathsf{NP}.

Un problema NP-completo es, entonces, un problema de NP al que se reducen todos los demás. De la definición y de los tres hechos salen las dos consecuencias que importan.

Teorema. Si BB es NP-completo y B∈PB \in \mathsf{P}, entonces P=NP\mathsf{P} = \mathsf{NP}.

Demostración. Sea A∈NPA \in \mathsf{NP}. Como BB es NP-difícil, A≤pBA \leq_p B, y como B∈PB \in \mathsf{P}, el primer hecho da A∈PA \in \mathsf{P}. Entonces NP⊆P\mathsf{NP} \subseteq \mathsf{P}, y la otra inclusión ya la tenemos de la semana pasada. ∎

Teorema. Si BB es NP-completo, C∈NPC \in \mathsf{NP} y B≤pCB \leq_p C, entonces CC es NP-completo.

Demostración. Sea A∈NPA \in \mathsf{NP}. Entonces A≤pBA \leq_p B porque BB es NP-difícil, y B≤pCB \leq_p C por hipótesis. Por transitividad, A≤pCA \leq_p C. Eso vale para todo AA de NP, así que CC es NP-difícil, y está en NP por hipótesis. ∎

El segundo teorema es la receta de Algoritmos: para mostrar que un problema nuevo CC es NP-completo se muestra que está en NP y se reduce desde un problema NP-completo conocido hacia CC. La dirección es la misma que en la semana 10, donde se reducía desde un problema indecidible conocido hacia el nuevo.

Error común. Demostrar que un problema es NP-completo y olvidar mostrar que está en NP. La reducción desde 3-SAT solo prueba que es NP-difícil. El problema de la parada también es NP-difícil, y no está en NP: ni siquiera es decidible. La definición tiene dos partes y hay que escribir las dos, aunque la primera sean dos líneas: cuál es el certificado y por qué se comprueba en tiempo polinomial.

El primer problema NP-completo

La receta necesita un problema NP-completo para empezar, y ese primero no puede salir de la receta.

La dificultad. Para mostrar que un problema BB es NP-difícil sin apoyarse en otro, hay que dar una reducción A≤pBA \leq_p B para cada lenguaje AA de NP: conjunto independiente, coloreo, suma de subconjuntos, y también todos los problemas de NP que nadie ha estudiado ni nombrado. No se puede ir uno por uno. Hace falta una sola construcción que sirva para todos, y entonces solo puede usar lo que todos tienen en común. Por la definición de NP con máquinas, eso es:

para cada A∈NPA \in \mathsf{NP} existe una máquina de Turing no determinista NN que decide AA en tiempo polinomial.

Nada más. La reducción tiene que tomar una cadena ww y convertir la pregunta “¿acepta NN a ww?” en una pregunta del problema BB. Así que BB debe ser un problema lo bastante expresivo para describir la ejecución de una máquina de Turing cualquiera. Cook, en 1971, e independientemente Levin, mostraron que las fórmulas booleanas alcanzan.

Definición. Una fórmula booleana (Boolean formula) se arma con variables, que valen verdadero o falso, y las operaciones ∧\land (y), ∨\lor (o) y ¬\lnot (no). Una asignación (assignment) da un valor a cada variable. La fórmula es satisfacible si alguna asignación la hace verdadera.

SAT={ ⟨φ⟩:φ es una foˊrmula booleana satisfacible }\mathrm{SAT} = \{\, \langle \varphi \rangle : \varphi \text{ es una fórmula booleana satisfacible} \,\}

Por ejemplo, φ=(x∨y)∧(¬x∨¬y)\varphi = (x \lor y) \land (\lnot x \lor \lnot y) es satisfacible, con xx verdadera e yy falsa. En cambio x∧¬xx \land \lnot x no lo es.

SAT está en NP: el certificado es la asignación, y el verificador evalúa la fórmula, lo que toma un tiempo lineal en su longitud. Lo vieron la semana pasada. Lo nuevo es la otra mitad.

Teorema (Cook-Levin). SAT es NP-completo.

El plan de la demostración, que ocupa toda la sesión:

  1. Fijar un lenguaje A∈NPA \in \mathsf{NP} cualquiera y una máquina no determinista NN que lo decide en tiempo nkn^k.
  2. Escribir la ejecución de NN con una entrada ww como una tabla, el tableau, con una configuración por fila. La máquina acepta ww si y solo si existe una tabla así que llega a qacceptq_{\text{accept}}.
  3. Dar una fórmula φ\varphi cuyas variables dicen qué hay en cada celda de la tabla, y que es verdadera exactamente cuando la tabla es una ejecución de NN que acepta ww.
  4. Comprobar que φ\varphi tiene tamaño polinomial en n=∣w∣n = |w| y que se escribe en tiempo polinomial.

Con eso, w↦⟨φ⟩w \mapsto \langle \varphi \rangle es una reducción de AA a SAT. Como AA era cualquiera, SAT es NP-difícil.

Diagrama en dos partes. Arriba, la clase NP dibujada como una región con cuatro lenguajes adentro: conjunto independiente, 3-coloreo, suma de subconjuntos y, con borde punteado, los que nadie ha nombrado. De los cuatro sale una flecha hacia la misma caja, que dice: una sola construcción, el tableau de la máquina que decide el lenguaje. De esa caja sale una flecha gruesa hacia SAT, rotulada A ≤_p SAT. Una nota dice que lo único que todos tienen en común es una máquina no determinista de tiempo polinomial. Abajo, la cadena para un lenguaje A de NP, una máquina N que lo decide en tiempo n^k y una entrada w de longitud n: tres cajas unidas por flechas de doble sentido. N acepta w, es decir, w está en A; existe un tableau de lado t = n^k + 4 que acepta w; φ es satisfacible, es decir, ⟨φ⟩ está en SAT. La primera equivalencia es el lema del tableau y la segunda sale de los cuatro grupos de cláusulas y del lema de las ventanas.Diagrama en dos partes. Arriba, la clase NP dibujada como una región con cuatro lenguajes adentro: conjunto independiente, 3-coloreo, suma de subconjuntos y, con borde punteado, los que nadie ha nombrado. De los cuatro sale una flecha hacia la misma caja, que dice: una sola construcción, el tableau de la máquina que decide el lenguaje. De esa caja sale una flecha gruesa hacia SAT, rotulada A ≤_p SAT. Una nota dice que lo único que todos tienen en común es una máquina no determinista de tiempo polinomial. Abajo, la cadena para un lenguaje A de NP, una máquina N que lo decide en tiempo n^k y una entrada w de longitud n: tres cajas unidas por flechas de doble sentido. N acepta w, es decir, w está en A; existe un tableau de lado t = n^k + 4 que acepta w; φ es satisfacible, es decir, ⟨φ⟩ está en SAT. La primera equivalencia es el lema del tableau y la segunda sale de los cuatro grupos de cláusulas y del lema de las ventanas.
La reducción no mira el problema: mira la máquina que lo decide, y por eso sirve para todo NP a la vez. Las dos equivalencias de abajo son las dos mitades de la demostración.

Una máquina de ejemplo

Para tener algo concreto que mirar en cada paso de la demostración, usaremos una máquina no determinista muy pequeña. Decide el lenguaje de las cadenas binarias que contienen 11\mathtt{11}. Ese lenguaje es regular y no necesita no determinismo; la máquina se eligió por chica, y por tener una sola decisión que adivinar.

$ cat machines/contains_11.tm
# Acepta las cadenas binarias que contienen 11.
# No determinista: en q0, al leer un 1, sigue de largo o apuesta a que ahí empieza el 11.
states: q0 q1 q_accept q_reject
alphabet: 0 1
tape: 0 1 _
start: q0
accept: q_accept
reject: q_reject
delta:
q0 0 -> q0 0 R
q0 1 -> q0 1 R
q0 1 -> q1 1 R
q1 1 -> q_accept 1 R

Es el formato .tm de la semana 7 para máquinas no deterministas: hay dos líneas para el par (q0,1)(q_0, \mathtt{1}). En una máquina no determinista, δ(q,a)\delta(q, a) es un conjunto de movimientos, y cada línea es uno. Como tabla:

Estado Lee 0\mathtt{0} Lee 1\mathtt{1} Lee ⊔\sqcup
q0q_0 (q0,0,R)(q_0, \mathtt{0}, \mathrm{R}) (q0,1,R)(q_0, \mathtt{1}, \mathrm{R}) o (q1,1,R)(q_1, \mathtt{1}, \mathrm{R}) ninguno
q1q_1 ninguno (qaccept,1,R)(q_{\text{accept}}, \mathtt{1}, \mathrm{R}) ninguno

Una casilla con “ninguno” es un par sin línea: la rama que llega ahí no tiene cómo seguir, y rechaza. La máquina recorre la entrada hacia la derecha en q0q_0. Cada vez que lee un 1\mathtt{1} elige: seguir en q0q_0, o pasar a q1q_1 apostando a que el símbolo siguiente también es 1\mathtt{1}. Si acierta, acepta.

El programa run_ntm recorre el árbol de ejecuciones por niveles, como la simulación determinista de la semana 7, e imprime las configuraciones de cada nivel en el formato u q vu\,q\,v:

$ build/run_ntm machines/contains_11.tm 011
N = machines/contains_11.tm, no determinista; w = 011
paso 0:  q0 011
paso 1:  0 q0 11
paso 2:  01 q0 1  |  01 q1 1
paso 3:  011 q0 _  |  011 q1 _  |  011 q_accept _
acepta: hay una rama de 3 pasos
  q0 011
  0 q0 11
  01 q1 1
  011 q_accept _

En el paso 2 hay dos configuraciones, porque en el paso 1 la máquina leyó un 1\mathtt{1} en q0q_0. En el paso 3 hay tres, y una de ellas acepta. Con eso basta: una máquina no determinista acepta si alguna rama acepta. Con 010\mathtt{010} ninguna lo hace:

$ build/run_ntm machines/contains_11.tm 010
N = machines/contains_11.tm, no determinista; w = 010
paso 0:  q0 010
paso 1:  0 q0 10
paso 2:  01 q0 0  |  01 q1 0
paso 3:  010 q0 _
rechaza: todas las ramas se detuvieron sin aceptar

La rama que apostó en el paso 2 quedó en q1q_1 leyendo un 0\mathtt{0}, sin movimiento posible. La otra llegó al blanco y tampoco tiene cómo seguir.

Con una entrada de longitud nn, toda rama de esta máquina se detiene en a lo sumo nn pasos, porque en cada paso avanza una celda y al llegar al blanco ya no hay movimientos. Es una máquina de tiempo polinomial, como pide la demostración.

Dos convenciones sobre las máquinas, que vienen de la semana 7 y que la demostración va a usar:

  • La cinta es infinita solo hacia la derecha. Un movimiento L\mathrm{L} en la primera celda deja el cabezal donde está.
  • Desde qacceptq_{\text{accept}} y desde qrejectq_{\text{reject}} no sale ninguna transición.

El tableau

Fijamos para toda la demostración un lenguaje A∈NPA \in \mathsf{NP} y una máquina no determinista N=(Q,Σ,Γ,δ,q0,qaccept,qreject)N = (Q, \Sigma, \Gamma, \delta, q_0, q_{\text{accept}}, q_{\text{reject}}) que decide AA en tiempo nkn^k: con una entrada de longitud nn, toda rama de NN se detiene en a lo sumo nkn^k pasos. Si la cota de NN fuera otro polinomio, por ejemplo c nk+cc\,n^k + c, se pone esa expresión donde aquí dice nkn^k. La demostración solo usa que es un polinomio en nn.

Definición. Un tableau de lado tt para NN es una tabla de t×tt \times t celdas. Cada celda contiene un elemento de

C=Γ∪Q∪{#}C = \Gamma \cup Q \cup \{\mathtt{\#}\}

es decir, un símbolo de la cinta, un estado o el separador #\mathtt{\#}, que no está en Γ\Gamma ni en QQ.

Queremos que cada fila sea una configuración. Una configuración u q vu\,q\,v se escribe en una fila así:

#    u    q    v    #\mathtt{\#}\;\; u\;\; q\;\; v\;\; \mathtt{\#}

La primera celda y la última contienen #\mathtt{\#}. Entre ellas quedan t−2t - 2 celdas: una para el estado y t−3t - 3 para las primeras t−3t - 3 celdas de la cinta, con los blancos que hagan falta al final. El estado va justo a la izquierda de la celda que lee el cabezal, como en la semana 7.

Definición. Una fila de tt celdas es una configuración si empieza y termina con #\mathtt{\#}, tiene exactamente un estado, todas sus otras celdas son símbolos de Γ\Gamma, y a la derecha del estado hay al menos un símbolo de Γ\Gamma. Lo último dice que la celda que lee el cabezal está dentro de la fila: un estado nunca queda pegado a la #\mathtt{\#} derecha.

Una configuración cabe en una fila de tt celdas si el cabezal está en una de las primeras t−3t - 3 celdas de la cinta y todo lo que hay más allá de esas t−3t - 3 celdas es blanco. Las #\mathtt{\#} no son parte de la cinta: marcan dónde termina la fila, y la de la izquierda hace además que una ventana pueda saber que está junto a la primera celda de la cinta, donde un movimiento L\mathrm{L} se comporta distinto.

Definición. Un tableau de lado tt acepta ww si:

  1. la fila 1 es la configuración inicial de NN con ww, es decir, #  q0  w  ⊔⋯⊔  #\mathtt{\#}\; q_0\; w\; \sqcup \cdots \sqcup\; \mathtt{\#};
  2. cada fila es una configuración, y la que está debajo sale de ella por un paso de NN; o bien la fila ya está en qacceptq_{\text{accept}} y la que está debajo es igual;
  3. alguna fila está en qacceptq_{\text{accept}}.

La segunda parte de la condición 2 es una convención: una configuración que acepta se repite hasta llenar la tabla. Hace falta porque una rama puede aceptar en menos pasos que las filas que hay, y desde qacceptq_{\text{accept}} la máquina no tiene transiciones.

Para la máquina de ejemplo con w=011w = \mathtt{011}, la rama que acepta tiene 3 pasos y al final el cabezal está en la cuarta celda. Hacen falta 4 celdas de cinta, así que t−3≥4t - 3 \geq 4, y el tableau más chico es el de lado 7:

#        q0       0        1        1        _        #
#        0        q0       1        1        _        #
#        0        1        q1       1        _        #
#        0        1        1        q_accept _        #
#        0        1        1        q_accept _        #
#        0        1        1        q_accept _        #
#        0        1        1        q_accept _        #

Las cuatro primeras filas son las cuatro configuraciones de la rama. Las tres últimas repiten la que acepta. Cada fila tiene 7 celdas, y las columnas están alineadas con el nombre más largo, q_accept.

El tableau de lado 7 de contains_11.tm con la entrada 011, dibujado como una tabla de 7 por 7 celdas. La primera y la última columna contienen #. Entre ellas, cada fila tiene un estado, resaltado, y cuatro celdas de la cinta. Fila 1: # q0 0 1 1 _ #. Fila 2: # 0 q0 1 1 _ #. Fila 3: # 0 1 q1 1 _ #. Fila 4: # 0 1 1 q_accept _ #. Las filas 5, 6 y 7 son iguales a la fila 4. El estado baja en diagonal, una columna a la derecha en cada fila, hasta la fila 4. Una llave marca las filas 1 a 4 como las cuatro configuraciones de la rama que acepta, con 3 pasos, y otra marca las filas 5 a 7: la configuración que acepta se repite hasta llenar la tabla.El tableau de lado 7 de contains_11.tm con la entrada 011, dibujado como una tabla de 7 por 7 celdas. La primera y la última columna contienen #. Entre ellas, cada fila tiene un estado, resaltado, y cuatro celdas de la cinta. Fila 1: # q0 0 1 1 _ #. Fila 2: # 0 q0 1 1 _ #. Fila 3: # 0 1 q1 1 _ #. Fila 4: # 0 1 1 q_accept _ #. Las filas 5, 6 y 7 son iguales a la fila 4. El estado baja en diagonal, una columna a la derecha en cada fila, hasta la fila 4. Una llave marca las filas 1 a 4 como las cuatro configuraciones de la rama que acepta, con 3 pasos, y otra marca las filas 5 a 7: la configuración que acepta se repite hasta llenar la tabla.
Una configuración por fila, entre dos #. El estado ocupa una celda, justo a la izquierda de la que lee el cabezal, y la configuración que acepta se repite hasta la última fila.

¿De qué lado tiene que ser la tabla para una entrada de longitud nn? La máquina da a lo sumo nkn^k pasos. En cada paso el cabezal avanza a lo sumo una celda, así que después de nkn^k pasos está, cuando más, en la celda nk+1n^k + 1 de la cinta. Y la entrada ocupa n≤nk+1n \leq n^k + 1 celdas. Entonces alcanza con:

  • nk+1n^k + 1 filas, una por configuración;
  • nk+1n^k + 1 celdas de cinta, más la del estado, más las dos #\mathtt{\#}: nk+4n^k + 4 columnas.

Tomamos la tabla cuadrada, con

t=nk+4t = n^k + 4

Es la “tabla de nk×nkn^k \times n^k” de la demostración; el +4+4 son las dos #\mathtt{\#}, la celda del estado y la celda que el cabezal alcanza en el último paso. No cambia nada del argumento, pero hace que las cuentas cierren exactamente, y el programa necesita que cierren. Con la máquina de ejemplo, cuya cota es nn pasos, da t=n+4t = n + 4: para 011\mathtt{011}, el lado 7 de la tabla de arriba.

Lema (del tableau). NN acepta ww si y solo si existe un tableau de lado t=nk+4t = n^k + 4 que acepta ww.

Demostración. En las dos direcciones.

Si NN acepta ww: alguna rama acepta, con configuraciones C0,C1,…,CmC_0, C_1, \ldots, C_m, donde C0C_0 es la inicial, CmC_m está en qacceptq_{\text{accept}} y m≤nkm \leq n^k. En CiC_i el cabezal está cuando más en la celda i+1≤nk+1=t−3i + 1 \leq n^k + 1 = t - 3, y la máquina solo pudo escribir en las celdas por donde pasó, así que cada CiC_i cabe en una fila. Se pone CiC_i en la fila i+1i + 1, para i=0,…,mi = 0, \ldots, m, y CmC_m en todas las filas siguientes. Son a lo sumo nk+1≤tn^k + 1 \leq t filas distintas. La tabla cumple las tres condiciones.

Si existe un tableau que acepta ww: sea ii la primera fila que está en qacceptq_{\text{accept}}. Las filas 1,…,i1, \ldots, i son configuraciones, la primera es la inicial con ww, y cada una sale de la anterior por un paso de NN, porque ninguna antes de la ii está en qacceptq_{\text{accept}}. Eso es una rama de NN que acepta ww. ∎

La primera dirección usa la cota de tiempo: sin ella no sabríamos de qué tamaño hacer la tabla. La segunda no la usa.

Idea clave. El tableau cambia una pregunta sobre un proceso, “¿hay alguna forma de ejecutar NN que termine aceptando?”, por una pregunta sobre un objeto, “¿existe una tabla con estas propiedades?”. El no determinismo desaparece: todas las decisiones de la máquina están escritas en la tabla. Es la misma idea de las historias de cómputo de la semana 10, puesta en dos dimensiones.

Las variables de la fórmula

Ahora la fórmula. Tiene una variable por cada celda y cada cosa que la celda puede contener:

xi,j,scon 1≤i,j≤t y s∈Cx_{i,j,s} \qquad \text{con } 1 \leq i, j \leq t \text{ y } s \in C

La variable xi,j,sx_{i,j,s} se lee: “la celda de la fila ii y la columna jj contiene ss”. Son t2 ∣C∣t^2\,|C| variables, con ∣C∣=∣Γ∣+∣Q∣+1|C| = |\Gamma| + |Q| + 1.

Una asignación cualquiera de estas variables no describe una tabla: puede decir que una celda contiene dos cosas a la vez, o ninguna. La fórmula es la conjunción de cuatro grupos de cláusulas, y cada uno impone una condición:

φ=φcelda∧φinicio∧φpaso∧φacepta\varphi = \varphi_{\text{celda}} \land \varphi_{\text{inicio}} \land \varphi_{\text{paso}} \land \varphi_{\text{acepta}}
Grupo Qué dice
φcelda\varphi_{\text{celda}} Cada celda contiene exactamente un símbolo de CC
φinicio\varphi_{\text{inicio}} La fila 1 es la configuración inicial con ww
φpaso\varphi_{\text{paso}} Cada ventana de 2×32 \times 3 celdas es legal
φacepta\varphi_{\text{acepta}} Alguna celda contiene qacceptq_{\text{accept}}
Cuatro copias en pequeño del tableau de lado 7 de contains_11.tm con 011, una por grupo de cláusulas, con la zona de la que habla cada grupo. Grupo 1, φ_celda: un marco rodea las 49 celdas; cada celda contiene exactamente un símbolo, y se dice celda por celda. Grupo 2, φ_inicio: el marco rodea solo la fila 1, # q0 0 1 1 _ #, y las demás filas están atenuadas; son 7 cláusulas de un literal y es el único lugar donde aparece w. Grupo 3, φ_paso: tres marcos de 2 por 3 celdas, superpuestos en parte, muestran tres de las 30 posiciones de ventana; cada ventana tiene que ser legal. Grupo 4, φ_acepta: un marco punteado rodea toda la tabla y solo las cuatro celdas con q_accept, en la columna 5 de las filas 4 a 7, están sin atenuar; es una sola cláusula de 49 literales que pide que alguna celda contenga q_accept.Cuatro copias en pequeño del tableau de lado 7 de contains_11.tm con 011, una por grupo de cláusulas, con la zona de la que habla cada grupo. Grupo 1, φ_celda: un marco rodea las 49 celdas; cada celda contiene exactamente un símbolo, y se dice celda por celda. Grupo 2, φ_inicio: el marco rodea solo la fila 1, # q0 0 1 1 _ #, y las demás filas están atenuadas; son 7 cláusulas de un literal y es el único lugar donde aparece w. Grupo 3, φ_paso: tres marcos de 2 por 3 celdas, superpuestos en parte, muestran tres de las 30 posiciones de ventana; cada ventana tiene que ser legal. Grupo 4, φ_acepta: un marco punteado rodea toda la tabla y solo las cuatro celdas con q_accept, en la columna 5 de las filas 4 a 7, están sin atenuar; es una sola cláusula de 49 literales que pide que alguna celda contenga q_accept.
Los grupos 1, 2 y 4 hablan de celdas sueltas. Solo el grupo 3 relaciona una fila con la siguiente, y solo el grupo 2 depende de la entrada.

En C++. Un solucionador SAT no conoce los índices ii, jj, ss: en DIMACS las variables son los enteros 1,2,3,…1, 2, 3, \ldots Hay que elegir una numeración. En cook_levin.h, los elementos de CC se numeran desde 0, primero Γ\Gamma, después QQ y al final #\mathtt{\#}, y la variable xi,j,sx_{i,j,s} es el entero ((i - 1) * t + (j - 1)) * |C| + s + 1. Con la máquina de ejemplo, ∣C∣=3+4+1=8|C| = 3 + 4 + 1 = 8, y con t=7t = 7 las variables de las celdas son las 72⋅8=3927^2 \cdot 8 = 392 primeras. Es la misma técnica que usaron para el sudoku en Algoritmos, con una variable por cada fila, columna y dígito.

Grupo 1: cada celda tiene exactamente un símbolo

Para cada celda (i,j)(i, j) hay que decir dos cosas: contiene al menos un símbolo, y a lo sumo uno.

φcelda=⋀1≤i,j≤t[  (⋁s∈Cxi,j,s)  ∧⋀s,s′∈Cs≠s′(¬xi,j,s∨¬xi,j,s′)]\varphi_{\text{celda}} = \bigwedge_{1 \leq i, j \leq t} \Bigl[\; \Bigl( \bigvee_{s \in C} x_{i,j,s} \Bigr) \;\land \bigwedge_{\substack{s, s' \in C \\ s \neq s'}} \bigl( \lnot x_{i,j,s} \lor \lnot x_{i,j,s'} \bigr) \Bigr]

La primera parte es una cláusula con ∣C∣|C| literales. La segunda es una cláusula de dos literales por cada par de símbolos distintos, que dice “no los dos”: son ∣C∣(∣C∣−1)/2|C|(|C| - 1)/2 pares. Es la codificación de “exactamente uno” que usaron en Algoritmos.

Cuando una asignación cumple φcelda\varphi_{\text{celda}}, tiene sentido hablar de la tabla de esa asignación: la que tiene en cada celda el único símbolo cuya variable es verdadera. Los otros tres grupos hablan de esa tabla.

Grupo 2: la primera fila es la configuración inicial

Con w=w1w2⋯wnw = w_1 w_2 \cdots w_n, la fila 1 tiene que ser #  q0  w1⋯wn  ⊔⋯⊔  #\mathtt{\#}\; q_0\; w_1 \cdots w_n\; \sqcup \cdots \sqcup\; \mathtt{\#}. Se dice celda por celda:

φinicio=x1,1,#∧x1,2,q0∧x1,3,w1∧⋯∧x1,n+2,wn∧x1,n+3,⊔∧⋯∧x1,t−1,⊔∧x1,t,#\varphi_{\text{inicio}} = x_{1,1,\mathtt{\#}} \land x_{1,2,q_0} \land x_{1,3,w_1} \land \cdots \land x_{1,n+2,w_n} \land x_{1,n+3,\sqcup} \land \cdots \land x_{1,t-1,\sqcup} \land x_{1,t,\mathtt{\#}}

Son tt cláusulas de un solo literal. Este es el único lugar de la fórmula donde aparece ww. Los otros tres grupos dependen de la máquina y de tt, y son los mismos para todas las entradas de la misma longitud.

Grupo 4: alguna celda contiene el estado de aceptación

Antes del grupo difícil, el más corto:

φacepta=⋁1≤i,j≤txi,j,qaccept\varphi_{\text{acepta}} = \bigvee_{1 \leq i, j \leq t} x_{i,j,q_{\text{accept}}}

Una sola cláusula, con t2t^2 literales.

Con estos tres grupos la fórmula todavía no dice nada sobre la máquina. La tabla que tiene la configuración inicial en la fila 1 y qacceptq_{\text{accept}} en todas las demás celdas los cumple. Falta decir que cada fila sale de la anterior por un paso de NN, y ahí está toda la demostración.

Ventanas legales

Decir “la fila i+1i + 1 sale de la fila ii por un paso” parece necesitar una condición sobre dos filas enteras, de 2t2t celdas. Si se escribiera así, la fórmula tendría que enumerar pares de filas, y hay una cantidad exponencial. La salida es la observación que ya hicieron con las historias de cómputo en la semana 10: un paso solo cambia lo que está junto al cabezal. Para comprobar que una fila sale de la anterior basta mirar trozos pequeños, uno por uno.

Definición. Una ventana es un bloque de 2×32 \times 3 celdas del tableau: las columnas jj, j+1j + 1, j+2j + 2 de dos filas seguidas, ii e i+1i + 1. La escribimos con su fila de arriba y su fila de abajo:

a1a2a3b1b2b3\begin{array}{|c|c|c|} \hline a_1 & a_2 & a_3 \\ \hline b_1 & b_2 & b_3 \\ \hline \end{array}

En un tableau de lado tt hay (t−1)(t−2)(t - 1)(t - 2) ventanas: t−1t - 1 pares de filas seguidas y t−2t - 2 posiciones para la columna izquierda. Las ventanas se superponen: cada celda que no está en el borde aparece en varias.

Animación del tableau de contains_11.tm con 011, que se llena fila por fila. Al inicio solo está la fila 1, la configuración inicial # q0 0 1 1 _ #. En cada paso un marco de 2 por 3 celdas rodea al estado de la última fila escrita y a las tres celdas de abajo; esas tres celdas se escriben con el resultado de un movimiento y las otras cuatro de la fila bajan copiadas de la fila de arriba. Paso 1: de la fila 1 a la 2, δ(q0, 0) tiene un solo movimiento, (q0, 0, R), y la ventana # q0 0 pasa a # 0 q0. Paso 2: de la fila 2 a la 3, δ(q0, 1) tiene dos movimientos, (q0, 1, R) y (q1, 1, R); la tabla sigue el segundo y la ventana 0 q0 1 pasa a 0 1 q1. Paso 3: de la fila 3 a la 4, δ(q1, 1) tiene el movimiento (q_accept, 1, R) y la ventana 1 q1 1 pasa a 1 1 q_accept. Pasos 4, 5 y 6: la fila está en q_accept, que no tiene transiciones, y se repite entera hasta la fila 7. La tabla queda llena y contiene q_accept.Animación del tableau de contains_11.tm con 011, que se llena fila por fila. Al inicio solo está la fila 1, la configuración inicial # q0 0 1 1 _ #. En cada paso un marco de 2 por 3 celdas rodea al estado de la última fila escrita y a las tres celdas de abajo; esas tres celdas se escriben con el resultado de un movimiento y las otras cuatro de la fila bajan copiadas de la fila de arriba. Paso 1: de la fila 1 a la 2, δ(q0, 0) tiene un solo movimiento, (q0, 0, R), y la ventana # q0 0 pasa a # 0 q0. Paso 2: de la fila 2 a la 3, δ(q0, 1) tiene dos movimientos, (q0, 1, R) y (q1, 1, R); la tabla sigue el segundo y la ventana 0 q0 1 pasa a 0 1 q1. Paso 3: de la fila 3 a la 4, δ(q1, 1) tiene el movimiento (q_accept, 1, R) y la ventana 1 q1 1 pasa a 1 1 q_accept. Pasos 4, 5 y 6: la fila está en q_accept, que no tiene transiciones, y se repite entera hasta la fila 7. La tabla queda llena y contiene q_accept.
De una fila a la siguiente solo cambian las tres celdas de la ventana que tiene el estado en el centro. Todo lo demás se copia.

Definición. Una ventana es legal para NN si aparece en algún paso de NN. Con precisión: si existen un ancho t′≥4t' \geq 4 y dos filas de t′t' celdas que son configuraciones, # C #\mathtt{\#}\,C\,\mathtt{\#} y debajo # C′ #\mathtt{\#}\,C'\,\mathtt{\#}, tales que

  • C′C' sale de CC por un paso de NN, o bien CC está en qacceptq_{\text{accept}} y C′=CC' = C,

y la ventana es el bloque de tres columnas seguidas de esas dos filas.

Que una ventana sea legal depende solo de δ\delta. No depende de ww ni de tt: es una lista finita que se calcula una vez por máquina.

Con la máquina de ejemplo y el movimiento (q1,1,R)∈δ(q0,1)(q_1, \mathtt{1}, \mathrm{R}) \in \delta(q_0, \mathtt{1}), estas son tres ventanas legales y tres ilegales:

Seis ventanas de 2 por 3 celdas de la máquina contains_11.tm, en dos filas de tres. Arriba, las legales. La primera tiene arriba 0 q0 1 y abajo 0 1 q1: el estado está en el centro, aparece entre las filas 2 y 3 del tableau en las columnas 2 a 4, y ve el paso completo del movimiento (q1, 1, R). La segunda tiene arriba q0 1 1 y abajo 1 q1 1: el estado está a la izquierda, en las columnas 3 a 5 de las mismas filas, y ve el estado y lo que lee pero no lo que tiene a su izquierda. La tercera tiene arriba 0 1 1 y abajo 0 1 1: no tiene estado, está entre las filas 4 y 5 en las columnas 2 a 4, lejos del cabezal, y sus dos filas son iguales. Abajo, las ilegales, con la celda culpable marcada. La primera tiene arriba 0 q0 1 y abajo 0 0 q1: escribe un 0, y δ(q0, 1) solo permite escribir 1. La segunda tiene arriba 0 1 1 y abajo 0 0 1: cambia una celda que no está junto a ningún estado. La tercera tiene arriba q0 1 # y abajo 1 q1 #: el estado q1 queda pegado a la #.Seis ventanas de 2 por 3 celdas de la máquina contains_11.tm, en dos filas de tres. Arriba, las legales. La primera tiene arriba 0 q0 1 y abajo 0 1 q1: el estado está en el centro, aparece entre las filas 2 y 3 del tableau en las columnas 2 a 4, y ve el paso completo del movimiento (q1, 1, R). La segunda tiene arriba q0 1 1 y abajo 1 q1 1: el estado está a la izquierda, en las columnas 3 a 5 de las mismas filas, y ve el estado y lo que lee pero no lo que tiene a su izquierda. La tercera tiene arriba 0 1 1 y abajo 0 1 1: no tiene estado, está entre las filas 4 y 5 en las columnas 2 a 4, lejos del cabezal, y sus dos filas son iguales. Abajo, las ilegales, con la celda culpable marcada. La primera tiene arriba 0 q0 1 y abajo 0 0 q1: escribe un 0, y δ(q0, 1) solo permite escribir 1. La segunda tiene arriba 0 1 1 y abajo 0 0 1: cambia una celda que no está junto a ningún estado. La tercera tiene arriba q0 1 # y abajo 1 q1 #: el estado q1 queda pegado a la #.
Una ventana es legal si aparece en algún paso de la máquina. Las ilegales fallan cada una por una razón distinta: un movimiento que no está en δ, un cambio lejos del cabezal, una fila que no es una configuración.

Las dos primeras legales están entre las filas 2 y 3 del tableau de arriba, y la tercera entre las filas 4 y 5. La primera tiene el estado en el centro y ve el paso completo: el estado, lo que lee y lo que tiene a la izquierda. La segunda tiene el estado a la izquierda. La tercera está lejos del cabezal, y sus dos filas son iguales.

En la primera ilegal, la máquina escribe un 0\mathtt{0}, y δ(q0,1)\delta(q_0, \mathtt{1}) solo permite escribir 1\mathtt{1}. En la segunda cambia una celda que no está junto a ningún estado. En la tercera el estado q1q_1 queda pegado a la #\mathtt{\#}, y esa fila de abajo no es parte de ninguna configuración. El programa windows responde por cualquier ventana:

$ build/windows machines/contains_11.tm 0 q0 1 0 1 q1
0 q0 1
0 1 q1
legal
$ build/windows machines/contains_11.tm 0 q0 1 0 0 q1
0 q0 1
0 0 q1
ilegal

Las cuatro formas

Para programar la lista hay que saber qué ventanas aparecen en un paso. Sea pp la columna del estado en la fila de arriba. Un paso con el movimiento (r,b,D)∈δ(q,a)(r, b, D) \in \delta(q, a) cambia solo las columnas p−1p - 1, pp y p+1p + 1:

columna:    p-1  p   p+1            p-1  p   p+1            p-1  p   p+1
arriba:      x   q    a              x   q    a              #   q    a
abajo:       x   b    r              r   x    b              #   r    b
            movimiento R            movimiento L        L en la primera celda

Con R\mathrm{R}, el símbolo escrito bb queda donde estaba el estado y el estado nuevo rr avanza. Con L\mathrm{L}, el estado retrocede y el símbolo xx que tenía a la izquierda pasa a su derecha. Si a la izquierda está la #\mathtt{\#}, el cabezal ya está en la primera celda y no se mueve.

Una ventana ocupa tres columnas seguidas, y según dónde caiga respecto de pp ve todo el paso, una parte o nada. De ahí salen cuatro formas. En la tabla, (r,b,D)∈δ(q,a)(r, b, D) \in \delta(q, a) es un movimiento de la máquina.

Forma Arriba Abajo Cuándo
1. Estado en el centro x  q  ax\;q\;a, con x∈Γ∪{#}x \in \Gamma \cup \{\mathtt{\#}\} x  b  rx\;b\;r (r,b,R)∈δ(q,a)(r, b, \mathrm{R}) \in \delta(q, a)
r  x  br\;x\;b (r,b,L)∈δ(q,a)(r, b, \mathrm{L}) \in \delta(q, a) y x∈Γx \in \Gamma
#  r  b\mathtt{\#}\;r\;b (r,b,L)∈δ(q,a)(r, b, \mathrm{L}) \in \delta(q, a) y x=#x = \mathtt{\#}
2. Estado a la izquierda q  a  yq\;a\;y, con y∈Γ∪{#}y \in \Gamma \cup \{\mathtt{\#}\} b  r  yb\;r\;y (r,b,R)∈δ(q,a)(r, b, \mathrm{R}) \in \delta(q, a) y y∈Γy \in \Gamma
x  b  yx\;b\;y, para cada x∈Γx \in \Gamma (r,b,L)∈δ(q,a)(r, b, \mathrm{L}) \in \delta(q, a)
r  b  yr\;b\;y (r,b,L)∈δ(q,a)(r, b, \mathrm{L}) \in \delta(q, a)
3. Estado a la derecha z  x  qz\;x\;q, con z∈Γ∪{#}z \in \Gamma \cup \{\mathtt{\#}\} y x∈Γx \in \Gamma z  x  bz\;x\;b (r,b,R)∈δ(q,a)(r, b, \mathrm{R}) \in \delta(q, a) para algún aa
z  r  xz\;r\;x (r,b,L)∈δ(q,a)(r, b, \mathrm{L}) \in \delta(q, a) para algún aa
4. Sin estado y1  y2  y3y_1\;y_2\;y_3, con y2∈Γy_2 \in \Gamma e y1,y3∈Γ∪{#}y_1, y_3 \in \Gamma \cup \{\mathtt{\#}\}, no los dos #\mathtt{\#} y1  y2  y3y_1\;y_2\;y_3 siempre
r  y2  y3r\;y_2\;y_3 (r,b,R)∈δ(q,y1)(r, b, \mathrm{R}) \in \delta(q, y_1) para algún qq
b  y2  y3b\;y_2\;y_3 (r,b,L)∈δ(q,y1)(r, b, \mathrm{L}) \in \delta(q, y_1) para algún qq
y1  y2  ry_1\;y_2\;r y3∈Γy_3 \in \Gamma y (r,b,L)∈δ(q,a)(r, b, \mathrm{L}) \in \delta(q, a) para algunos qq, aa
Aceptación x  qaccept  ax\;q_{\text{accept}}\;a,   qaccept  a  x\;q_{\text{accept}}\;a\;x,   x  a  qaccept\;x\;a\;q_{\text{accept}}, con a∈Γa \in \Gamma y x∈Γ∪{#}x \in \Gamma \cup \{\mathtt{\#}\} igual a la de arriba siempre

Cada línea sale de mirar el dibujo del paso desde una ventana corrida:

  • Forma 1. La ventana ocupa las columnas p−1p - 1, pp, p+1p + 1: ve todo lo que cambia, y su fila de abajo es exactamente el resultado de un movimiento.
  • Forma 2. La ventana ocupa pp, p+1p + 1, p+2p + 2. Ve el estado y lo que lee, pero no el símbolo xx de su izquierda. Con L\mathrm{L}, ese símbolo desconocido baja a su primera celda, y por eso vale cualquier x∈Γx \in \Gamma; o el cabezal estaba en la primera celda y se queda. Con R\mathrm{R}, el estado nuevo queda en la columna p+1p + 1 y necesita leer la p+2p + 2: si ahí está la #\mathtt{\#}, la configuración siguiente no cabe en la fila, y no hay ventana legal.
  • Forma 3. La ventana ocupa p−2p - 2, p−1p - 1, pp. No ve qué lee el estado, así que vale el efecto de cualquier movimiento desde qq.
  • Forma 4. No hay estado en la fila de arriba. Si el estado está lejos, nada cambia. Si está justo a la izquierda de la ventana, lee y1y_1 y puede cambiar esa celda. Si está justo a la derecha, puede entrar con un movimiento L\mathrm{L}. La celda del centro siempre se copia.
  • Aceptación. La convención de repetir la configuración que acepta.

El programa las cuenta:

$ build/windows machines/contains_11.tm
|Γ| = 3, |Q| = 4, |C| = 8
ventanas posibles: 8^6 = 262144
ventanas legales:  193
  con el estado en el centro:    28
  con el estado a la izquierda:  24
  con el estado a la derecha:    48
  sin estado arriba:             93

De las 868^6 maneras de llenar seis celdas con ocho símbolos, 193 son legales. La opción --lista las escribe todas. Las que tienen arriba x  q0  1x\;q_0\;\mathtt{1}, por ejemplo, son ocho: dos movimientos posibles por cuatro valores de xx.

$ build/windows machines/contains_11.tm --lista | grep ' q0 1 /'
0 q0 1 / 0 1 q0
0 q0 1 / 0 1 q1
1 q0 1 / 1 1 q0
1 q0 1 / 1 1 q1
_ q0 1 / _ 1 q0
_ q0 1 / _ 1 q1
# q0 1 / # 1 q0
# q0 1 / # 1 q1

La tabla de las cuatro formas es una manera de calcular la lista, y la definición es la de arriba: aparecer en un paso. Que las dos coinciden se comprueba mirando los casos, y también por fuerza bruta: test_tableau recorre todas las configuraciones de la máquina en filas con hasta 6 celdas entre las dos #\mathtt{\#} (7 con las máquinas más chicas), da todos los pasos posibles, junta las ventanas que aparecen y compara con lo que da la tabla. Lo hace con las máquinas de machines/ y con 30 máquinas al azar.

Sea L\mathcal{L} el conjunto de las ventanas legales de NN. El grupo dice que en cada una de las (t−1)(t−2)(t - 1)(t - 2) posiciones hay alguna de ellas:

φpaso=⋀1≤i≤t−11≤j≤t−2    ⋁(a1a2a3/b1b2b3) ∈ L(xi,j,a1∧xi,j+1,a2∧xi,j+2,a3∧xi+1,j,b1∧xi+1,j+1,b2∧xi+1,j+2,b3)\varphi_{\text{paso}} = \bigwedge_{\substack{1 \leq i \leq t-1 \\ 1 \leq j \leq t-2}} \;\; \bigvee_{(a_1 a_2 a_3 / b_1 b_2 b_3) \,\in\, \mathcal{L}} \bigl( x_{i,j,a_1} \land x_{i,j+1,a_2} \land x_{i,j+2,a_3} \land x_{i+1,j,b_1} \land x_{i+1,j+1,b_2} \land x_{i+1,j+2,b_3} \bigr)

Para cada posición (i,j)(i, j) hay una disyunción con un término por ventana legal, y cada término es la conjunción de seis variables: “en estas seis celdas está exactamente esta ventana”. Esta parte de la fórmula no está en CNF, y para el teorema no hace falta: SAT admite cualquier fórmula. En la sesión B la pasamos a CNF.

Por qué bastan las ventanas

Falta la parte de la demostración que justifica todo lo anterior: si la fila de arriba es una configuración y todas las ventanas entre dos filas son legales, la fila de abajo es una configuración que sale de la de arriba por un paso. No es evidente. Las ventanas se revisan por separado, y con una máquina no determinista cada una podría, en principio, corresponder a un movimiento distinto.

De la definición de ventana legal salen cuatro propiedades. En todas, la ventana aparece en un paso entre dos filas que son configuraciones, con el estado de la fila de arriba en la columna pp.

  • (P1) Sin estado arriba, el centro se copia. Si a1a_1, a2a_2, a3a_3 no son estados, entonces b2=a2b_2 = a_2. Por qué: un paso solo cambia las columnas p−1p - 1, pp y p+1p + 1. Si la columna del centro fuera una de esas, alguna de las tres columnas de la ventana sería la pp, y arriba habría un estado.
  • (P2) Con el estado en el centro, la ventana ve el paso completo. Si a2=qa_2 = q es un estado distinto de qacceptq_{\text{accept}}, entonces b1 b2 b3b_1\,b_2\,b_3 es lo que deja en las columnas p−1p - 1, pp, p+1p + 1 un movimiento (r,b,D)∈δ(q,a3)(r, b, D) \in \delta(q, a_3), como en el dibujo del paso. Si a2=qaccepta_2 = q_{\text{accept}}, la fila de abajo es igual a la de arriba. Por qué: las tres columnas de la ventana son justo las que el paso cambia.
  • (P3) Las #\mathtt{\#} no se mueven. b1=#b_1 = \mathtt{\#} si y solo si a1=#a_1 = \mathtt{\#}, y lo mismo con b3b_3 y a3a_3. Por qué: en las dos filas, las #\mathtt{\#} están en la primera y en la última columna, y en ninguna otra.
  • (P4) Ningún estado queda pegado a la #\mathtt{\#} derecha. En una ventana legal no pasa que b2b_2 sea un estado y b3=#b_3 = \mathtt{\#}. Por qué: la fila de abajo es una configuración.

Lema (de las ventanas). Sea la fila ii de una tabla una configuración # C #\mathtt{\#}\,C\,\mathtt{\#}, y supongamos que las t−2t - 2 ventanas entre las filas ii e i+1i + 1 son legales. Entonces la fila i+1i + 1 es una configuración # C′ #\mathtt{\#}\,C'\,\mathtt{\#}, y o bien C′C' sale de CC por un paso de NN, o bien CC está en qacceptq_{\text{accept}} y C′=CC' = C.

Demostración. Directa, columna por columna. Sean a1,…,ata_1, \ldots, a_t las celdas de la fila ii y b1,…,btb_1, \ldots, b_t las de la fila i+1i + 1. Como la fila ii es una configuración, tiene un solo estado, q=apq = a_p, con 2≤p≤t−22 \leq p \leq t - 2. A su derecha está el símbolo que lee, a=ap+1∈Γa = a_{p+1} \in \Gamma, y a su izquierda x=ap−1x = a_{p-1}, que es un símbolo de Γ\Gamma o, si p=2p = 2, la #\mathtt{\#}.

Las tres columnas del cabezal. La ventana de las columnas p−1p - 1, pp, p+1p + 1 existe, porque 1≤p−11 \leq p - 1 y p+1≤t−1p + 1 \leq t - 1, y tiene el estado en el centro. Por (P2), bp−1 bp bp+1b_{p-1}\,b_p\,b_{p+1} es el resultado de un solo movimiento (r,b,D)∈δ(q,a)(r, b, D) \in \delta(q, a), o es una copia si q=qacceptq = q_{\text{accept}}. Aquí se elige el movimiento, una sola vez y para las tres celdas juntas.

Las demás columnas. Sea cc una columna distinta de p−1p - 1, pp y p+1p + 1. Si 2≤c≤t−12 \leq c \leq t - 1, la ventana de las columnas c−1c - 1, cc, c+1c + 1 no tiene ningún estado arriba, porque ninguna de las tres es la pp. Por (P1), bc=acb_c = a_c. Si c=1c = 1 o c=tc = t, la celda aca_c es #\mathtt{\#} y está en la esquina de una ventana, y por (P3) bc=#b_c = \mathtt{\#}.

Entonces la fila i+1i + 1 es la fila ii con las columnas p−1p - 1, pp, p+1p + 1 cambiadas por el resultado del movimiento elegido. Eso es, celda por celda, lo que el movimiento hace con CC.

La fila de abajo es una configuración. Tiene las #\mathtt{\#} en su lugar, un solo estado y símbolos de Γ\Gamma en lo demás. Falta ver que el estado tiene una celda a su derecha. Si el movimiento es L\mathrm{L} o es la copia, el estado queda en la columna p−1p - 1 o en la pp, y a su derecha hay un símbolo. Si es R\mathrm{R}, el estado rr queda en la columna p+1p + 1. La ventana de las columnas pp, p+1p + 1, p+2p + 2 existe, porque p≤t−2p \leq t - 2, y tiene abajo a rr en el centro. Por (P4), bp+2≠#b_{p+2} \neq \mathtt{\#}: hay una celda de cinta a la derecha de rr.

Así que la fila i+1i + 1 es la configuración C′C' que deja ese movimiento, y C′C' cabe en la fila. ∎

La demostración muestra dónde está el peligro y por qué no ocurre. Las ventanas vecinas a la del cabezal (formas 2 y 3) admiten varios movimientos, pero comparten celdas con la ventana del centro, y esa ya fijó las tres celdas que cambian. Las ventanas se superponen, y la superposición las obliga a ponerse de acuerdo.

Animación del lema de las ventanas con las filas 2 y 3 del tableau de contains_11.tm con 011. La fila 2 es # 0 q0 1 1 _ #, con el estado en la columna 3, y la fila 3 empieza con signos de pregunta. Paso 1, propiedad P2: un marco rodea la ventana de las columnas 2 a 4, que tiene el estado en el centro; abajo queda lo que deja un solo movimiento de δ(q0, 1), que puede ser 0 1 q0 o 0 1 q1, y la tabla tiene 0 1 q1. Paso 2, propiedad P1: las ventanas de las columnas 4 a 6 y 5 a 7 no tienen estado arriba, y su celda del centro se copia; quedan escritas las columnas 5 y 6, con 1 y blanco. Paso 3, propiedad P3: las ventanas de las columnas 1 a 3 y 5 a 7 tienen una # en la esquina de arriba, y debajo de una # hay una #; quedan las columnas 1 y 7. Paso 4: la ventana de las columnas 3 a 5, sola, admitiría abajo 1 q0 1 o 1 q1 1, pero comparte las columnas 3 y 4 con la ventana de las columnas 2 a 4, que ya eligió. Paso 5, propiedad P4: en la ventana de las columnas 3 a 5 el estado q1 queda abajo en el centro y a su derecha no hay una #; la fila 3, # 0 1 q1 1 _ #, es la configuración que deja el movimiento (q1, 1, R).Animación del lema de las ventanas con las filas 2 y 3 del tableau de contains_11.tm con 011. La fila 2 es # 0 q0 1 1 _ #, con el estado en la columna 3, y la fila 3 empieza con signos de pregunta. Paso 1, propiedad P2: un marco rodea la ventana de las columnas 2 a 4, que tiene el estado en el centro; abajo queda lo que deja un solo movimiento de δ(q0, 1), que puede ser 0 1 q0 o 0 1 q1, y la tabla tiene 0 1 q1. Paso 2, propiedad P1: las ventanas de las columnas 4 a 6 y 5 a 7 no tienen estado arriba, y su celda del centro se copia; quedan escritas las columnas 5 y 6, con 1 y blanco. Paso 3, propiedad P3: las ventanas de las columnas 1 a 3 y 5 a 7 tienen una # en la esquina de arriba, y debajo de una # hay una #; quedan las columnas 1 y 7. Paso 4: la ventana de las columnas 3 a 5, sola, admitiría abajo 1 q0 1 o 1 q1 1, pero comparte las columnas 3 y 4 con la ventana de las columnas 2 a 4, que ya eligió. Paso 5, propiedad P4: en la ventana de las columnas 3 a 5 el estado q1 queda abajo en el centro y a su derecha no hay una #; la fila 3, # 0 1 q1 1 _ #, es la configuración que deja el movimiento (q1, 1, R).
La ventana con el estado en el centro elige el movimiento, una sola vez. Las demás copian, y las vecinas comparten celdas con ella: no les queda nada que elegir.

El lema también vale al revés, y esa dirección es inmediata: si C′C' sale de CC por un paso y las dos caben, todas las ventanas entre sus filas son legales, porque “aparecer en un paso” es la definición.

test_tableau comprueba el lema sin pasar por la demostración. Para cada configuración que cabe en una fila de 4, 5 o 6 celdas, busca todas las filas de abajo que dejan legales las ventanas, probando los ∣C∣|C| símbolos en cada celda, y compara con las configuraciones que da un paso de la máquina:

test_tableau: ok (el lema de las ventanas con 5358 filas)

Idea clave. La máquina de Turing es local: en un paso solo cambia lo que está junto al cabezal. Por eso una condición sobre toda la tabla se puede partir en condiciones sobre trozos de tamaño fijo, y por eso la fórmula tiene un tamaño razonable. Las historias de cómputo de la semana 10 usaban la misma localidad con fichas de PCP y con gramáticas. Aquí se usa con cláusulas.

El tamaño de la fórmula

Una reducción tiene que calcularse en tiempo polinomial, así que hay que contar. Sea t=nk+4t = n^k + 4 y sea L=∣L∣L = |\mathcal{L}| la cantidad de ventanas legales. Las cantidades ∣C∣|C| y LL dependen de la máquina y no de la entrada: para la demostración son constantes. Como una ventana tiene seis celdas, L≤∣C∣6L \leq |C|^6.

Parte Cuánto mide
Variables xi,j,sx_{i,j,s} t2 ∣C∣t^2\,\lvert C\rvert variables
φcelda\varphi_{\text{celda}} t2t^2 celdas, cada una con ∣C∣+∣C∣(∣C∣−1)\lvert C\rvert + \lvert C\rvert(\lvert C\rvert - 1) literales
φinicio\varphi_{\text{inicio}} tt literales
φpaso\varphi_{\text{paso}} (t−1)(t−2)(t - 1)(t - 2) posiciones, cada una con 6L6L literales
φacepta\varphi_{\text{acepta}} t2t^2 literales

En total hay O(t2)=O(n2k)O(t^2) = O(n^{2k}) variables y O(n2k)O(n^{2k}) literales, con constantes que dependen de NN. Cada variable se escribe con su número, que tiene O(log⁡n)O(\log n) dígitos, así que la fórmula ocupa O(n2klog⁡n)O(n^{2k} \log n) símbolos. Es un polinomio en nn.

Y se escribe en tiempo polinomial. La lista de ventanas legales se calcula una vez, mirando δ\delta. Después, la fórmula son cuatro ciclos sobre las celdas, que escriben siempre el mismo patrón. La reducción no ejecuta la máquina: solo copia su tabla de transiciones, convertida en ventanas, en cada posición de la tabla.

La respuesta a la pregunta de repaso 3 queda así: si la máquina corre en tiempo nkn^k, la fórmula tiene

t2 ∣C∣=(nk+4)2 (∣Γ∣+∣Q∣+1)t^2\,|C| = (n^k + 4)^2 \, (|\Gamma| + |Q| + 1)

variables.

La fórmula es satisfacible si y solo si la máquina acepta

Con los dos lemas, lo que queda es corto.

Afirmación. φ\varphi es satisfacible si y solo si NN acepta ww.

Demostración. Por el lema del tableau, basta mostrar que φ\varphi es satisfacible si y solo si existe un tableau de lado tt que acepta ww.

Si existe un tableau que acepta ww: se hace verdadera xi,j,sx_{i,j,s} exactamente cuando la celda (i,j)(i, j) del tableau contiene ss. Cada celda tiene un solo símbolo, y se cumple φcelda\varphi_{\text{celda}}. La fila 1 es la configuración inicial, y se cumple φinicio\varphi_{\text{inicio}}. Dos filas seguidas son un paso de NN o la repetición de una configuración que acepta, así que cada ventana entre ellas aparece en un paso: es legal por definición, y se cumple φpaso\varphi_{\text{paso}}. Alguna fila está en qacceptq_{\text{accept}}, y se cumple φacepta\varphi_{\text{acepta}}.

Si φ\varphi es satisfacible: se toma una asignación que la cumple. Por φcelda\varphi_{\text{celda}} describe una tabla. Por φinicio\varphi_{\text{inicio}}, la fila 1 es la configuración inicial con ww, que es una configuración porque n≤t−3n \leq t - 3. Por φpaso\varphi_{\text{paso}} todas las ventanas son legales, y el lema de las ventanas, aplicado a las filas 1,2,…,t−11, 2, \ldots, t - 1 por inducción, dice que cada fila es una configuración que sale de la anterior por un paso, o la repite si ya aceptó. Por φacepta\varphi_{\text{acepta}}, alguna celda contiene qacceptq_{\text{accept}}: alguna fila está en ese estado. La tabla es un tableau que acepta ww. ∎

Demostración del teorema de Cook-Levin. SAT está en NP. Para ver que es NP-difícil, sea AA un lenguaje de NP y NN una máquina no determinista que lo decide en tiempo nkn^k. La función ff que a cada ww le asigna ⟨φ⟩\langle \varphi \rangle, la fórmula construida con NN, ww y t=∣w∣k+4t = |w|^k + 4, se calcula en tiempo polinomial, y

w∈A  ⟺  N acepta w  ⟺  φ es satisfacible  ⟺  f(w)∈SATw \in A \iff N \text{ acepta } w \iff \varphi \text{ es satisfacible} \iff f(w) \in \mathrm{SAT}

Entonces A≤pSATA \leq_p \mathrm{SAT}. Como AA era un lenguaje cualquiera de NP, SAT es NP-difícil. ∎

Hay una reducción distinta para cada lenguaje AA, porque cada uno tiene su máquina y su exponente kk. Lo que es común a todas es la manera de construir la fórmula.

La reducción, ejecutada

Todo lo anterior se puede correr. El programa tableau_cnf recibe una máquina, una entrada y el lado tt, y escribe la fórmula en DIMACS. El lado se da a mano: el programa no sabe cuál es la cota de tiempo de la máquina. Lo que garantiza, por los dos lemas, es esto:

la fórmula es satisfacible si y solo si NN acepta ww con una ejecución que cabe en el tableau de lado tt: a lo sumo t−1t - 1 pasos, y el cabezal dentro de las primeras t−3t - 3 celdas de la cinta.

Con tt igual a la cota de tiempo más 4 caben todas las ejecuciones, y es el teorema.

$ build/tableau_cnf machines/contains_11.tm 011 7 > build/f.cnf
$ minisat -verb=0 build/f.cnf build/f.res
SATISFIABLE
$ build/decode_tableau machines/contains_11.tm 011 7 build/f.res
#        q0       0        1        1        _        #
#        0        q0       1        1        _        #
#        0        1        q1       1        _        #
#        0        1        1        q_accept _        #
#        0        1        1        q_accept _        #
#        0        1        1        q_accept _        #
#        0        1        1        q_accept _        #
es una ejecución de la máquina: acepta en 3 pasos

minisat deja en build/f.res una asignación de las variables. decode_tableau mira, en cada celda, cuál de sus ocho variables es verdadera, imprime la tabla y la comprueba sin usar la fórmula: revisa con el simulador que cada fila sale de la anterior por un paso de la máquina. Es el tableau que escribimos a mano unas secciones atrás.

Miren la fila 3. En la fila 2 la máquina estaba en q0q_0 leyendo un 1\mathtt{1}, y tenía dos movimientos. Nadie programó cuál elegir: en ningún lugar del generador hay una búsqueda. La fórmula solo dice que alguna celda debe contener q_accept, y minisat encontró que para eso la fila 3 debía tener q1.

Con t=6t = 6 la fórmula no se puede cumplir, aunque la máquina acepta 011\mathtt{011}:

$ build/tableau_cnf machines/contains_11.tm 011 6 > build/g.cnf
$ minisat -verb=0 build/g.cnf build/g.res
UNSATISFIABLE
$ build/decode_tableau machines/contains_11.tm 011 6 build/g.res
UNSAT: ningún tableau de 6 × 6 acepta

En una fila de 6 celdas hay 3 de cinta, y la rama que acepta termina con el cabezal en la cuarta. La ejecución no cabe. Por eso en la demostración importa elegir el lado con cuidado: una tabla demasiado chica cambia la respuesta. Y con una entrada que la máquina rechaza, ningún lado sirve:

$ build/tableau_cnf machines/contains_11.tm 010 8 > build/g.cnf
$ minisat -verb=0 build/g.cnf build/g.res
UNSATISFIABLE

Con una máquina determinista hay un solo tableau posible, y minisat no tiene nada que elegir. Esta es la máquina de {0n1n}\{\mathtt{0}^n\mathtt{1}^n\} de la semana 7 con la entrada 01\mathtt{01}, que acepta en 5 pasos:

$ build/tableau_cnf machines/zeros_ones.tm 01 7 > build/g.cnf
$ minisat -verb=0 build/g.cnf build/g.res
SATISFIABLE
$ build/decode_tableau machines/zeros_ones.tm 01 7 build/g.res
#        q0       0        1        _        _        #
#        X        q1       1        _        _        #
#        q2       X        Y        _        _        #
#        X        q0       Y        _        _        #
#        X        Y        q3       _        _        #
#        X        Y        _        q_accept _        #
#        X        Y        _        q_accept _        #
es una ejecución de la máquina: acepta en 5 pasos

De la fila 2 a la fila 3 el estado retrocede, y el símbolo X que tenía a la izquierda pasa a su derecha: es la segunda línea de la forma 1.

Cuánto mide

La opción --cuenta dice cuántas variables y cláusulas tiene la fórmula que escribe el programa. Su grupo 3 está ya en CNF, con unas variables adicionales que se explican en la sesión B; por eso hay “variables de ventanas”.

$ build/tableau_cnf machines/contains_11.tm 011 7 --cuenta
t = 7, |C| = 8, ventanas legales = 193
variables de celdas:    392
variables de ventanas:  5790
variables en total:     6182
cláusulas del grupo 1:  1421
cláusulas del grupo 2:  7
cláusulas del grupo 3:  34770
cláusulas del grupo 4:  1
cláusulas en total:     36199

Las cuentas de la sección anterior dan esos números. Las variables de las celdas son t2 ∣C∣=49⋅8=392t^2\,|C| = 49 \cdot 8 = 392. El grupo 1 tiene, por celda, una cláusula de “al menos uno” y 8⋅7/2=288 \cdot 7 / 2 = 28 de “no los dos”: 49⋅29=142149 \cdot 29 = 1421. El grupo 2 tiene t=7t = 7. El grupo 3 tiene (t−1)(t−2)=30(t - 1)(t - 2) = 30 posiciones de ventana.

Al crecer tt, todo crece como t2t^2:

tt Variables Cláusulas
5 2516 14 639
10 14 696 86 359
20 69 206 407 999
40 298 826 1 764 079

Son las salidas de build/tableau_cnf machines/contains_11.tm 11 t --cuenta para cada tt. Al duplicar tt, las cláusulas se multiplican por 5,9, por 4,7 y por 4,3: se acercan a 4, que es lo que da un polinomio de grado 2. Para una máquina fija, la fórmula es cuadrática en el lado de la tabla.

La constante es grande. Una máquina de cuatro estados con una entrada de tres símbolos da una fórmula de 36 199 cláusulas. Con la máquina de {0n1n}\{\mathtt{0}^n\mathtt{1}^n\}, que tiene 1109 ventanas legales, la tabla de lado 7 da 202 941. Nadie resuelve un problema así; la reducción existe para demostrar el teorema.

Error común. Creer que la fórmula “simula” a la máquina. La fórmula no calcula nada: es una lista de condiciones que describe cómo se vería una ejecución que acepta. Encontrar esa ejecución es trabajo de quien resuelve SAT, y ahí queda toda la dificultad. Tampoco la reducción simula: para escribir la fórmula se mira la tabla de transiciones y la longitud de ww, y no se da ni un paso de la máquina. Si la reducción tuviera que recorrer el árbol de ejecuciones para escribir la fórmula, tardaría un tiempo exponencial y no sería una reducción.

En la práctica. Esta manera de usar un solucionador SAT tiene nombre en la industria: verificación acotada de modelos (bounded model checking). Para saber si un circuito o un protocolo puede llegar a un estado de error en tt pasos, se escribe una fórmula con una copia de las variables del sistema por cada paso, cláusulas que dicen que cada copia sale de la anterior, y una cláusula que dice que alguna copia es el error. Es el tableau, con el estado de un circuito en lugar de la configuración de una máquina.

De la fórmula del tableau a una fórmula en CNF

La sesión A terminó con SAT NP-completo. Para diseñar reducciones, SAT es incómodo: una fórmula cualquiera tiene paréntesis anidados y operaciones mezcladas. En Algoritmos todas las reducciones partían de 3-SAT, donde la fórmula es una lista de cláusulas de tres literales. Esta sesión baja de SAT a 3-SAT en dos escalones, y en los dos aparece la misma idea.

Definición. Un literal es una variable o su negación. Una cláusula (clause) es una disyunción de literales. Una fórmula está en forma normal conjuntiva, o CNF, si es una conjunción de cláusulas.

El primer escalón es mostrar que SAT sigue siendo NP-completo cuando la fórmula está en CNF. Para eso alcanza con escribir en CNF la fórmula del tableau. Tres de sus cuatro grupos ya lo están:

Grupo Forma ¿CNF?
φcelda\varphi_{\text{celda}} Cláusulas de ∣C∣\lvert C\rvert literales y de 2 literales sí
φinicio\varphi_{\text{inicio}} tt cláusulas de 1 literal sí
φacepta\varphi_{\text{acepta}} 1 cláusula de t2t^2 literales sí
φpaso\varphi_{\text{paso}} Conjunción de disyunciones de conjunciones no

Queda φpaso\varphi_{\text{paso}}. Para cada posición de ventana tiene una subfórmula de esta forma, con un término por ventana legal:

W1∨W2∨⋯∨WLdonde cada Wk es una conjuncioˊn de 6 variablesW_1 \lor W_2 \lor \cdots \lor W_L \qquad \text{donde cada } W_k \text{ es una conjunción de 6 variables}

Hay tres maneras de pasarla a CNF. Las tres sirven para el teorema y solo una sirve para programar.

Primera manera: distribuir

La ley distributiva convierte una disyunción de conjunciones en una conjunción de disyunciones: (p∧q)∨(r∧s)(p \land q) \lor (r \land s) equivale a (p∨r)∧(p∨s)∧(q∨r)∧(q∨s)(p \lor r) \land (p \lor s) \land (q \lor r) \land (q \lor s). Hay una cláusula por cada manera de elegir un literal de cada término. Con LL términos de 6 literales salen 6L6^L cláusulas, cada una de LL literales.

Eso es exponencial en LL. Pero LL depende de la máquina y no de la entrada: para una NN fija, 6L6^L es una constante, y la fórmula en CNF sigue teniendo tamaño O(n2k)O(n^{2k}). Para la demostración alcanza. Para un programa, no: con la máquina de ejemplo, L=193L = 193 y 61936^{193} es un número de 151 dígitos, porque 193⋅log⁡106≈193⋅0,778=150,2193 \cdot \log_{10} 6 \approx 193 \cdot 0{,}778 = 150{,}2.

Si se distribuyera una fórmula cualquiera, la constante dejaría de serlo. La fórmula (x1∧y1)∨(x2∧y2)∨⋯∨(xm∧ym)(x_1 \land y_1) \lor (x_2 \land y_2) \lor \cdots \lor (x_m \land y_m) tiene 2m2m literales, y al distribuirla salen 2m2^m cláusulas. Por eso “pasar a CNF” con equivalencias no es, en general, una reducción de tiempo polinomial.

Segunda manera: prohibir las ventanas ilegales

Cuando se cumple φcelda\varphi_{\text{celda}}, en cada posición hay exactamente una ventana: la que forman los seis símbolos de esas celdas. Decir “es alguna de las legales” es lo mismo que decir “no es ninguna de las ilegales”, y lo segundo ya es CNF. Por cada posición y cada ventana ilegal se pone una cláusula de seis literales negados:

¬xi,j,a1∨¬xi,j+1,a2∨¬xi,j+2,a3∨¬xi+1,j,b1∨¬xi+1,j+1,b2∨¬xi+1,j+2,b3\lnot x_{i,j,a_1} \lor \lnot x_{i,j+1,a_2} \lor \lnot x_{i,j+2,a_3} \lor \lnot x_{i+1,j,b_1} \lor \lnot x_{i+1,j+1,b_2} \lor \lnot x_{i+1,j+2,b_3}

Son ∣C∣6−L|C|^6 - L cláusulas por posición, sin variables nuevas. Con la máquina de ejemplo, 262 144−193=261 951262\,144 - 193 = 261\,951. Es una constante mucho más razonable que 61936^{193}, y aun así la tabla de lado 7, con sus 30 posiciones, tendría 30⋅261 951=7 858 53030 \cdot 261\,951 = 7\,858\,530 cláusulas solo en este grupo.

Tercera manera: variables nuevas

Es la que usa tableau_cnf. Por cada posición (i,j)(i, j) y cada ventana legal kk se agrega una variable nueva zkz_k, que se lee “en esta posición está la ventana kk”. La subfórmula W1∨⋯∨WLW_1 \lor \cdots \lor W_L se reemplaza por estas cláusulas:

(z1∨z2∨⋯∨zL)y, para cada k y cada una de las seis variables x de Wk,(¬zk∨x)(z_1 \lor z_2 \lor \cdots \lor z_L) \qquad\text{y, para cada } k \text{ y cada una de las seis variables } x \text{ de } W_k, \qquad (\lnot z_k \lor x)

La primera dice que alguna ventana legal está en esa posición. Las otras dicen que, si la elegida es la kk, sus seis celdas contienen lo que la ventana kk dice: (¬zk∨x)(\lnot z_k \lor x) es la implicación zk→xz_k \to x. Son 6L+16L + 1 cláusulas y LL variables nuevas por posición. Con la máquina de ejemplo, 6⋅193+1=11596 \cdot 193 + 1 = 1159 cláusulas en lugar de 261 951. Con las 30 posiciones de la tabla de lado 7 dan las 34 770 cláusulas del grupo 3 y las 5790 “variables de ventanas” que informó --cuenta.

La fórmula nueva no es equivalente a la vieja: tiene otras variables, y ni siquiera tiene sentido comparar sus tablas de verdad. Lo que se conserva es otra cosa.

Afirmación. Para cada asignación de las variables xx: se cumple W1∨⋯∨WLW_1 \lor \cdots \lor W_L si y solo si existen valores de z1,…,zLz_1, \ldots, z_L con los que se cumplen todas las cláusulas nuevas.

Demostración. En las dos direcciones.

Si se cumple W1∨⋯∨WLW_1 \lor \cdots \lor W_L: algún WkW_k es verdadero. Se pone zkz_k verdadera y todas las demás zz falsas. La cláusula larga se cumple por zkz_k. Las cláusulas (¬zm∨x)(\lnot z_m \lor x) con m≠km \neq k se cumplen porque zmz_m es falsa. Las seis con zkz_k se cumplen porque las seis variables de WkW_k son verdaderas.

Si existen esos valores de las zz: por la cláusula larga, alguna zkz_k es verdadera. Las seis cláusulas (¬zk∨x)(\lnot z_k \lor x) obligan entonces a que las seis variables de WkW_k sean verdaderas. WkW_k se cumple. ∎

Entonces la fórmula con las zz es satisfacible si y solo si la original lo es, y de una asignación que cumple la nueva, la parte de las xx cumple la original. Por eso decode_tableau puede leer el tableau mirando solo las primeras t2 ∣C∣t^2\,|C| variables e ignorar las demás.

Idea clave. Una reducción no tiene que producir una fórmula equivalente. Tiene que conservar la respuesta: satisfacible va a satisfacible, e insatisfacible a insatisfacible. Dos fórmulas así se llaman equisatisfacibles. Agregar variables nuevas que nombran partes de la fórmula es la manera de evitar el crecimiento exponencial, y vuelve a aparecer en el escalón siguiente.

Lo mismo se puede hacer con cualquier fórmula, no solo con la del tableau. Se agrega una variable nueva ygy_g por cada subfórmula gg, con unas pocas cláusulas que dicen que ygy_g vale lo que vale gg en función de las variables de sus partes. Por ejemplo, para g=h1∧h2g = h_1 \land h_2 son (¬yg∨yh1)(\lnot y_g \lor y_{h_1}), (¬yg∨yh2)(\lnot y_g \lor y_{h_2}) y (yg∨¬yh1∨¬yh2)(y_g \lor \lnot y_{h_1} \lor \lnot y_{h_2}). Al final se agrega la cláusula de un literal que dice que la variable de la fórmula completa es verdadera. La fórmula que sale está en CNF, tiene un tamaño lineal en el de la original y es equisatisfacible con ella. Se llama transformación de Tseitin, y es lo que hacen las herramientas que le pasan un circuito a un solucionador SAT. Con eso, SAT≤pCNF-SAT\mathrm{SAT} \leq_p \mathrm{CNF\text{-}SAT} para toda fórmula.

De CNF a 3-SAT

El segundo escalón es acortar las cláusulas.

Definición. En 3-SAT, la entrada es una fórmula en CNF en la que cada cláusula tiene exactamente tres literales, de tres variables distintas. La pregunta es si es satisfacible.

Es la definición de Algoritmos. Sipser permite que una cláusula repita un literal; las dos versiones son NP-completas con la misma demostración.

Teorema. 3-SAT es NP-completo.

Demostración. Por reducción desde SAT en CNF, que es NP-completo por lo anterior. La dirección es la de siempre: desde el problema que ya se sabe difícil, hacia el nuevo.

Está en NP: una fórmula de 3-SAT es una fórmula, y el certificado es la asignación.

Qué se construye. Cada cláusula se limpia y se reemplaza. Limpiar es quitar los literales repetidos y borrar la cláusula si contiene una variable y su negación, porque siempre se cumple. Una cláusula limpia de kk literales, (ℓ1∨ℓ2∨⋯∨ℓk)(\ell_1 \lor \ell_2 \lor \cdots \lor \ell_k), se reemplaza según kk. Las variables yy son nuevas y no se comparten entre cláusulas.

kk Se reemplaza por
1 (ℓ1∨y1∨y2)∧(ℓ1∨y1∨¬y2)∧(ℓ1∨¬y1∨y2)∧(ℓ1∨¬y1∨¬y2)(\ell_1 \lor y_1 \lor y_2) \land (\ell_1 \lor y_1 \lor \lnot y_2) \land (\ell_1 \lor \lnot y_1 \lor y_2) \land (\ell_1 \lor \lnot y_1 \lor \lnot y_2)
2 (ℓ1∨ℓ2∨y1)∧(ℓ1∨ℓ2∨¬y1)(\ell_1 \lor \ell_2 \lor y_1) \land (\ell_1 \lor \ell_2 \lor \lnot y_1)
3 la misma cláusula
k≥4k \geq 4 la cadena de abajo, con k−3k - 3 variables nuevas y k−2k - 2 cláusulas
(ℓ1∨ℓ2∨y1)∧(¬y1∨ℓ3∨y2)∧(¬y2∨ℓ4∨y3)∧⋯∧(¬yk−4∨ℓk−2∨yk−3)∧(¬yk−3∨ℓk−1∨ℓk)(\ell_1 \lor \ell_2 \lor y_1) \land (\lnot y_1 \lor \ell_3 \lor y_2) \land (\lnot y_2 \lor \ell_4 \lor y_3) \land \cdots \land (\lnot y_{k-4} \lor \ell_{k-2} \lor y_{k-3}) \land (\lnot y_{k-3} \lor \ell_{k-1} \lor \ell_k)

Una cláusula vacía, que no se puede cumplir, se reemplaza por las 8 cláusulas sobre tres variables nuevas, que tampoco se pueden cumplir todas.

En la cadena, ymy_m se lee “el literal verdadero está más adelante, después de ℓm+1\ell_{m+1}”. La primera cláusula dice: es ℓ1\ell_1, es ℓ2\ell_2 o está más adelante. Cada una del medio dice: si está más adelante de ℓm\ell_m, entonces es ℓm+1\ell_{m+1} o está todavía más adelante. La última ya no puede pasar el encargo.

El programa three_sat aplica la construcción. Con la cláusula de la pregunta de repaso 4:

$ build/three_sat --ver < formulas/five.cnf
entrada, con 5 variables y 1 cláusulas:
  (x1 ∨ x2 ∨ x3 ∨ x4 ∨ x5)
salida, con 7 variables y 3 cláusulas:
  (x1 ∨ x2 ∨ x6)
  (¬x6 ∨ x3 ∨ x7)
  (¬x7 ∨ x4 ∨ x5)

Las variables nuevas son x6 y x7: son y1y_1 e y2y_2, con el número siguiente al de la última variable de la entrada.

Por qué conserva la respuesta. Como las variables nuevas de cada cláusula son solo suyas, alcanza con mostrar, para una cláusula cc y lo que la reemplaza, que una asignación de las variables originales cumple cc si y solo si se puede extender a las variables nuevas de modo que se cumpla todo el reemplazo. Limpiar no cambia cuándo se cumple una cláusula.

Cadena, si la asignación cumple cc: sea ℓm\ell_m el primer literal verdadero. Se pone yjy_j verdadera para j≤m−2j \leq m - 2 y falsa para j≥m−1j \geq m - 1: las yy anteriores al literal verdadero dicen “está más adelante”, y las siguientes ya no. Hay que revisar las tres clases de cláusulas.

  • La primera, (ℓ1∨ℓ2∨y1)(\ell_1 \lor \ell_2 \lor y_1): si m≤2m \leq 2 se cumple por ℓm\ell_m; si m≥3m \geq 3, y1y_1 es verdadera.
  • Una del medio, (¬yj−1∨ℓj+1∨yj)(\lnot y_{j-1} \lor \ell_{j+1} \lor y_j), con 2≤j≤k−32 \leq j \leq k - 3: si j≤m−2j \leq m - 2, yjy_j es verdadera. Si j=m−1j = m - 1, el literal del medio es ℓm\ell_m, que es verdadero. Si j≥mj \geq m, yj−1y_{j-1} es falsa.
  • La última, (¬yk−3∨ℓk−1∨ℓk)(\lnot y_{k-3} \lor \ell_{k-1} \lor \ell_k): si m≥k−1m \geq k - 1 se cumple por ℓm\ell_m; si m≤k−2m \leq k - 2, entonces k−3≥m−1k - 3 \geq m - 1 e yk−3y_{k-3} es falsa.

Cadena, si la asignación no cumple cc: todos los ℓ\ell son falsos, y ninguna elección de las yy sirve. La primera cláusula obliga a y1y_1 verdadera. Con y1y_1 verdadera y ℓ3\ell_3 falso, la segunda obliga a y2y_2 verdadera. Así hasta yk−3y_{k-3} verdadera, y entonces la última cláusula tiene sus tres literales falsos.

Cláusulas cortas. Con k=2k = 2: si cc se cumple, las dos cláusulas se cumplen con cualquier y1y_1; si no, una pide y1y_1 y la otra ¬y1\lnot y_1. Con k=1k = 1 es igual, con las cuatro combinaciones de y1y_1 e y2y_2.

Tiempo polinomial. Una cláusula de kk literales produce a lo sumo max⁡(k−2,8)\max(k - 2, 8) cláusulas, así que la salida es lineal en la entrada. ∎

Error común. Decir que la fórmula de 3-SAT “es equivalente” a la original. No lo es. Con la cláusula de cinco literales y la asignación que hace verdadera solo a x5x_5, la salida de arriba se cumple si x6x_6 y x7x_7 son verdaderas, y no se cumple si x6x_6 es falsa: la primera cláusula quedaría con sus tres literales falsos. La misma asignación de las variables originales sirve o no según las variables nuevas. Lo que se conserva es que exista una asignación.

Aplicada a la fórmula del tableau de la sesión A, la construcción parte sobre todo las cláusulas largas: las 30 de 193 literales del grupo 3 y la de 49 del grupo 4. Y rellena las cortas, que son la mayoría.

$ build/three_sat < build/f.cnf > build/f3.cnf
entrada: 6182 variables, 36199 cláusulas, la más larga de 193 literales
salida:  48299 variables, 78323 cláusulas, todas de 3 literales
$ minisat -verb=0 build/f3.cnf build/f3.res
SATISFIABLE
$ build/decode_tableau machines/contains_11.tm 011 7 build/f3.res

El último comando imprime el mismo tableau de antes, y termina con es una ejecución de la máquina: acepta en 3 pasos. Las variables de las celdas conservan sus números, así que el decodificador no nota la diferencia. Con t=6t = 6, la fórmula de 3-SAT es insatisfacible, igual que la original.

Juntando las dos sesiones: de una máquina no determinista y una entrada sale, en tiempo polinomial, una fórmula de 3-SAT que es satisfacible exactamente cuando la máquina acepta.

Lo que queda demostrado hasta el fondo

Con 3-SAT NP-completo, todo lo que hicieron en las semanas 13 y 14 de Algoritmos queda apoyado en una demostración completa. Ahí redujeron 3-SAT a conjunto independiente, con un triángulo por cláusula; 3-SAT a 3-coloreo, con gadgets de variable y de cláusula; conjunto independiente a cobertura de vértices y a clique; y cobertura de vértices a suma de subconjuntos. No repetimos esas construcciones. Lo que cambia es lo que se puede concluir de ellas.

todo lenguaje de NP
        │   Cook-Levin: el tableau
        ▼
       SAT
        │   variables nuevas
        ▼
      3-SAT ──► conjunto independiente ──► cobertura de vértices ──► suma de subconjuntos
        │               └──► clique
        ├──► 3-coloreo
        └──► camino hamiltoniano (la sección siguiente)

Cada flecha es una reducción en tiempo polinomial, y las reducciones se componen. Antes de esta semana, el dibujo empezaba en SAT y decía “estos problemas son al menos tan difíciles como SAT”. Ahora empieza en todo NP: cualquier problema de NP se reduce a cualquiera de los de abajo. Y como todos los de abajo están en NP, se reducen también entre sí, pasando por SAT. Son, en un sentido preciso, el mismo problema escrito de maneras distintas.

De ahí la frase que resume la teoría: basta que uno solo de ellos esté en P para que todos lo estén, y con ellos todo NP. Un algoritmo polinomial para colorear grafos con tres colores sería también uno para la suma de subconjuntos, para SAT y para cualquier problema cuyas soluciones se puedan verificar rápido. Y al revés: si alguno no está en P, ninguno lo está.

Se conocen miles de problemas NP-completos, de todas las áreas: horarios, rutas, empaquetado, plegamiento de proteínas, rompecabezas. Ninguno tiene un algoritmo polinomial conocido, y de ninguno se ha demostrado que no lo tenga.

De 3-SAT a camino hamiltoniano

Una reducción nueva, de un estilo distinto a las de Algoritmos. Allá, los gadgets usaban aristas para prohibir combinaciones: dos literales opuestos no podían estar juntos en el conjunto independiente. Aquí los gadgets obligan a un camino a recorrer el grafo de cierta manera.

Definición. Un camino hamiltoniano en un grafo dirigido es un camino que pasa por cada nodo exactamente una vez.

HAMPATH={ ⟨G,s,t⟩:G es un grafo dirigido con un camino hamiltoniano de s a t }\mathrm{HAMPATH} = \{\, \langle G, s, t \rangle : G \text{ es un grafo dirigido con un camino hamiltoniano de } s \text{ a } t \,\}

Teorema. HAMPATH es NP-completo.

Está en NP. Lo vieron la semana pasada: el certificado es la lista de los nodos en el orden del camino, y el verificador comprueba que están todos una vez, que empieza en ss, termina en tt y que cada par de nodos seguidos es una arista.

Es NP-difícil. Por reducción desde 3-SAT: de una fórmula φ\varphi se construye ⟨G,s,t⟩\langle G, s, t \rangle de modo que φ\varphi es satisfacible si y solo si GG tiene un camino hamiltoniano de ss a tt.

La construcción

Sea φ\varphi una fórmula con variables x1,…,xlx_1, \ldots, x_l y cláusulas c1,…,ckc_1, \ldots, c_k. El grafo tiene tres clases de piezas.

Un rombo por variable. El rombo de xix_i tiene una punta de arriba, did_i, una punta de abajo, que es la punta de arriba del rombo siguiente, di+1d_{i+1}, y una fila horizontal de nodos entre dos extremos, izq y der. De la punta de arriba salen aristas a los dos extremos, y de los dos extremos salen aristas a la punta de abajo. Los nodos de la fila están unidos con sus vecinos en los dos sentidos.

          ┌───────────────────────── d_i ─────────────────────────┐
          ▼                                                       ▼
         izq ⇄ sep0 ⇄ c1a ⇄ c1b ⇄ sep1 ⇄ c2a ⇄ c2b ⇄ sep2 ⇄ ··· ⇄ der
          │                                                       │
          └───────────────────────► d_i+1 ◄───────────────────────┘

Un camino que entra por did_i y tiene que pasar por toda la fila tiene dos opciones: bajar a izq y recorrer la fila de izquierda a derecha, o bajar a der y recorrerla de derecha a izquierda. Esa elección va a ser el valor de xix_i: de izquierda a derecha es verdadero, de derecha a izquierda es falso.

La fila tiene un par de nodos por cláusula. Entre izq y der hay 3k+13k + 1 nodos: para cada cláusula cjc_j, un par de nodos seguidos, cja y cjb, y entre los pares, antes del primero y después del último, un nodo separador. Son 2k2k nodos de pares y k+1k + 1 separadores.

Un nodo por cláusula, con desvíos. Cada cláusula cjc_j tiene un nodo propio, fuera de los rombos. Se conecta con el par de cjc_j en el rombo de cada variable que aparece en ella:

x_i aparece en c_j                      ¬x_i aparece en c_j

          c_j                                     c_j
         ↗   ↘                                   ↙   ↖
··· ⇄ cja ⇄ cjb ⇄ ···                   ··· ⇄ cja ⇄ cjb ⇄ ···

Si xix_i aparece en cjc_j, las aristas son cja →cj→\to c_j \to cjb: un desvío que solo se puede tomar recorriendo la fila de izquierda a derecha. Si aparece ¬xi\lnot x_i, son cjb →cj→\to c_j \to cja: solo de derecha a izquierda.

Finalmente, s=d1s = d_1 y t=dl+1t = d_{l+1}.

El grafo tiene (l+1)+l (3k+3)+k(l + 1) + l\,(3k + 3) + k nodos: las puntas, las filas con sus dos extremos, y los nodos de cláusula. Las aristas son 4l4l de los rombos, 2l (3k+2)2l\,(3k + 2) de las filas y 2 por cada literal de la fórmula. Todo es polinomial en el tamaño de φ\varphi, y se escribe recorriendo la fórmula una vez.

El programa hampath construye el grafo y busca el camino con backtracking. Con la fórmula (x1∨x2∨¬x3)∧(¬x1∨x2∨x3)(x_1 \lor x_2 \lor \lnot x_3) \land (\lnot x_1 \lor x_2 \lor x_3):

$ build/hampath < formulas/two_clauses.cnf
fórmula: 3 variables, 2 cláusulas
  (x1 ∨ x2 ∨ ¬x3)
  (¬x1 ∨ x2 ∨ x3)
grafo: 33 nodos, 72 aristas
camino hamiltoniano de s a t:
  s x1.izq x1.sep0 x1.c1a x1.c1b x1.sep1 x1.c2a x1.c2b x1.sep2 x1.der d2 x2.izq x2.sep0 x2.c1a
  x2.c1b x2.sep1 x2.c2a c2 x2.c2b x2.sep2 x2.der d3 x3.der x3.sep2 x3.c2b x3.c2a x3.sep1 x3.c1b c1
  x3.c1a x3.sep0 x3.izq t
asignación leída del camino: x1 = V x2 = V x3 = F
cumple la fórmula

Las cuentas dan 4+3⋅9+2=334 + 3 \cdot 9 + 2 = 33 nodos y 12+6⋅8+2⋅6=7212 + 6 \cdot 8 + 2 \cdot 6 = 72 aristas. En el camino, los rombos de x1x_1 y x2x_2 se recorren de izquierda a derecha y el de x3x_3 de derecha a izquierda. El nodo c2 se visita con un desvío desde el rombo de x2x_2, entre x2.c2a y x2.c2b: la cláusula 2 tiene a x2x_2, que es verdadera. El nodo c1 se visita desde el rombo de x3x_3, entre x3.c1b y x3.c1a: la cláusula 1 tiene a ¬x3\lnot x_3, y x3x_3 es falsa.

Con las ocho cláusulas posibles sobre tres variables, que ninguna asignación cumple a la vez, no hay camino:

$ build/hampath < formulas/all_eight.cnf
...
grafo: 93 nodos, 216 aristas
no hay camino hamiltoniano de s a t

Una dirección, completa

Afirmación. Si φ\varphi es satisfacible, GG tiene un camino hamiltoniano de ss a tt.

Demostración. Por construcción del camino. Se toma una asignación que cumple φ\varphi.

El camino sin desvíos. Para i=1,…,li = 1, \ldots, l, en orden: desde did_i, si xix_i es verdadera se va a izq, se recorre la fila de izquierda a derecha hasta der, y se baja a di+1d_{i+1}. Si es falsa, se va a der, se recorre la fila de derecha a izquierda hasta izq, y se baja a di+1d_{i+1}. Todas esas aristas existen. El camino empieza en d1=sd_1 = s, termina en dl+1=td_{l+1} = t y pasa una vez por cada nodo de los rombos. Solo le faltan los nodos de cláusula.

Los desvíos. Para cada cláusula cjc_j se elige uno de sus literales verdaderos; existe porque la asignación cumple φ\varphi.

  • Si el elegido es xix_i, entonces xix_i es verdadera y la fila de su rombo se recorre de izquierda a derecha: el camino pasa de cja a cjb. Ese paso se reemplaza por cja →cj→\to c_j \to cjb, que son las dos aristas que se pusieron por aparecer xix_i en cjc_j.
  • Si el elegido es ¬xi\lnot x_i, entonces xix_i es falsa y la fila se recorre de derecha a izquierda: el camino pasa de cjb a cja. Se reemplaza por cjb →cj→\to c_j \to cja.

Es hamiltoniano. Cada nodo de cláusula se agrega una sola vez, porque se eligió un solo literal. Los desvíos no se estorban: el de cjc_j reemplaza un paso dentro del par de cjc_j, y cláusulas distintas tienen pares distintos. El resultado es un camino de ss a tt que pasa una vez por cada nodo. ∎

test_hampath hace exactamente esto con cada asignación que cumple cada fórmula de prueba: construye el camino con la función path_from_assignment y comprueba que es hamiltoniano.

La otra dirección, en una idea

Afirmación. Si GG tiene un camino hamiltoniano de ss a tt, φ\varphi es satisfacible.

No la demostramos completa. La idea es que un camino hamiltoniano no tiene más remedio que ser como los de arriba: recorre los rombos en orden, cada fila entera en un solo sentido, y cada desvío vuelve al mismo par del que salió. Lo único que podría romper eso es un camino que entra a un nodo de cláusula desde un rombo y sale hacia otro rombo. Los separadores existen para impedirlo.

Supongan que el camino recorre la fila de xix_i de izquierda a derecha, llega a cja, pasa a cjc_j, y de ahí sale a otro rombo. El nodo cjb de ese par quedó sin visitar. A cjb solo llegan aristas desde cja, desde cjc_j y desde el separador de su derecha. Los dos primeros ya están usados: el sucesor de cja en el camino es cjc_j, y el de cjc_j es un nodo de otro rombo. Entonces a cjb solo se puede llegar desde el separador. Pero de cjb solo salen aristas hacia cja, que ya fue visitado, y hacia ese mismo separador. El camino moriría en cjb, que no es tt. Los otros casos se tratan igual: siempre queda un nodo de la fila al que solo se puede entrar y salir por el mismo vecino.

Entonces el camino es de la forma normal, y de él se lee una asignación: xix_i es verdadera si su fila se recorre de izquierda a derecha. Cada nodo de cláusula cjc_j se visita con un desvío desde algún rombo, y por cómo están orientadas sus aristas, ese desvío solo se puede tomar si el literal correspondiente es verdadero. Cada cláusula tiene un literal verdadero.

test_hampath comprueba las dos direcciones con 210 fórmulas pequeñas: la búsqueda encuentra un camino exactamente cuando la fuerza bruta dice que la fórmula es satisfacible, y la asignación leída del camino siempre cumple la fórmula.

De aquí salen más problemas. El camino hamiltoniano en grafos no dirigidos también es NP-completo, y de él se llega al problema del viajante. El contraste que vieron en Algoritmos sigue ahí: pasar una vez por cada arista es fácil, y se decide mirando los grados; pasar una vez por cada nodo es NP-completo.

2-SAT está en P

La construcción de la cadena parte cláusulas hasta dejarlas de tres literales. ¿Por qué no seguir hasta dos? Porque no se puede: al partir (ℓ1∨ℓ2∨ℓ3)(\ell_1 \lor \ell_2 \lor \ell_3) con una variable nueva sale (ℓ1∨ℓ2∨y)∧(¬y∨ℓ3)(\ell_1 \lor \ell_2 \lor y) \land (\lnot y \lor \ell_3), y la primera sigue teniendo tres. El eslabón necesita un lugar para el literal propio, uno para recibir el encargo y otro para pasarlo. Y no es una limitación de esta construcción: del otro lado del borde, el problema es fácil.

Teorema. 2-SAT, la satisfacibilidad de fórmulas en CNF con cláusulas de dos literales, está en P.

Lo vieron al final de Algoritmos, y lo recordamos con su criterio. Una cláusula (a∨b)(a \lor b) dice dos implicaciones: si aa es falso, bb es verdadero, y si bb es falso, aa es verdadero. El grafo de implicaciones tiene un nodo por cada literal y, por cada cláusula (a∨b)(a \lor b), las aristas ¬a→b\lnot a \to b y ¬b→a\lnot b \to a.

Criterio. Una fórmula de 2-SAT es satisfacible si y solo si ninguna variable xx tiene a xx y a ¬x\lnot x en la misma componente fuertemente conexa del grafo de implicaciones.

Idea de la demostración. Una asignación que cumple la fórmula no puede tener una arista de un literal verdadero a uno falso, y entonces tampoco un camino. Si xx y ¬x\lnot x están en la misma componente, hay caminos de xx a ¬x\lnot x y de ¬x\lnot x a xx; uno de los dos literales es verdadero y el otro falso, y uno de los dos caminos iría de verdadero a falso. No hay asignación.

Al revés, si ninguna variable tiene sus dos literales en la misma componente, se ordenan las componentes topológicamente y se hace verdadero, de cada par xx, ¬x\lnot x, el literal cuya componente queda más tarde en el orden. Que eso no deja ninguna arista de verdadero a falso sale de la simetría del grafo: la arista a→ba \to b existe si y solo si existe ¬b→¬a\lnot b \to \lnot a. ∎

Las componentes fuertemente conexas se calculan en tiempo lineal, con el algoritmo que vieron en Algoritmos. Por ejemplo, (x∨y)∧(¬x∨y)∧(x∨¬y)∧(¬x∨¬y)(x \lor y) \land (\lnot x \lor y) \land (x \lor \lnot y) \land (\lnot x \lor \lnot y) da las aristas

¬x→y,¬y→x,x→y,¬y→¬x,¬x→¬y,y→x,x→¬y,y→¬x\lnot x \to y,\quad \lnot y \to x,\quad x \to y,\quad \lnot y \to \lnot x,\quad \lnot x \to \lnot y,\quad y \to x,\quad x \to \lnot y,\quad y \to \lnot x

y con ellas x→y→¬x→¬y→xx \to y \to \lnot x \to \lnot y \to x: los cuatro literales están en una sola componente, y la fórmula no se puede cumplir. Son las cuatro cláusulas posibles sobre dos variables.

Idea clave. El borde entre lo fácil y lo difícil pasa entre 2 y 3. Con dos literales por cláusula, fijar un valor obliga a otro, y una cadena de obligaciones es un camino en un grafo. Con tres, fijar un valor solo deja una alternativa entre dos, y las alternativas se multiplican. El mismo borde aparece en el coloreo: con 2 colores es un recorrido del grafo, y con 3 es NP-completo.

coNP

NP está hecho de preguntas cuya respuesta sí tiene un certificado corto. La definición no trata igual al sí y al no, y eso se ve al dar vuelta un problema.

UNSAT={ ⟨φ⟩:φ no es satisfacible }TAUTOLOGY={ ⟨φ⟩:toda asignacioˊn cumple φ }\mathrm{UNSAT} = \{\, \langle \varphi \rangle : \varphi \text{ no es satisfacible} \,\} \qquad \mathrm{TAUTOLOGY} = \{\, \langle \varphi \rangle : \text{toda asignación cumple } \varphi \,\}

Los dos son, en el fondo, el mismo problema: φ\varphi es una tautología si y solo si ¬φ\lnot \varphi no es satisfacible. Para convencer a alguien de que una fórmula es satisfacible basta mostrarle una asignación. ¿Qué se le muestra para convencerlo de que no lo es? La lista de las 2n2^n asignaciones, todas fallando, no es un certificado corto. Nadie conoce uno.

Recuerden la definición de la semana 12: coNP\mathsf{coNP} es la clase de los lenguajes cuyo complemento está en NP:

coNP={ A:A‾∈NP }\mathsf{coNP} = \{\, A : \overline{A} \in \mathsf{NP} \,\}

Un lenguaje está en coNP si las respuestas no tienen certificado corto. UNSAT, que la semana 12 escribió SAT‾\overline{\mathrm{SAT}}, está en coNP, porque su complemento es SAT, salvo por las cadenas que no son fórmulas, que se reconocen en tiempo polinomial. TAUTOLOGY también.

coNP\mathsf{coNP} no es el complemento de NP\mathsf{NP} como conjunto de lenguajes. Las dos clases se superponen. P es cerrada bajo complemento, porque en una máquina determinista que siempre se detiene se pueden intercambiar aceptar y rechazar, y entonces

P⊆NP∩coNP\mathsf{P} \subseteq \mathsf{NP} \cap \mathsf{coNP}

Un lenguaje de NP∩coNP\mathsf{NP} \cap \mathsf{coNP} tiene certificados cortos para las dos respuestas. El ejemplo más conocido es la factorización, escrita como problema de decisión: dados nn y mm, ¿tiene nn un divisor dd con 1<d≤m1 < d \leq m? Para el sí, el certificado es el divisor. Para el no, es la factorización completa de nn en primos, todos mayores que mm: se multiplican para comprobar que dan nn, y que cada factor es primo se comprueba en tiempo polinomial. No se sabe si este problema está en P, y casi nadie cree que sea NP-completo, por lo que sigue.

Teorema. Si algún lenguaje NP-completo está en coNP, entonces NP=coNP\mathsf{NP} = \mathsf{coNP}.

Demostración. Sea BB NP-completo con B∈coNPB \in \mathsf{coNP}, es decir, B‾∈NP\overline{B} \in \mathsf{NP}.

NP⊆coNP\mathsf{NP} \subseteq \mathsf{coNP}: sea A∈NPA \in \mathsf{NP}. Hay una reducción ff con w∈A  ⟺  f(w)∈Bw \in A \iff f(w) \in B. Negando los dos lados, w∈A‾  ⟺  f(w)∈B‾w \in \overline{A} \iff f(w) \in \overline{B}: la misma ff reduce A‾\overline{A} a B‾\overline{B}. Como B‾∈NP\overline{B} \in \mathsf{NP}, también A‾∈NP\overline{A} \in \mathsf{NP}: el certificado de ww es el de f(w)f(w). Entonces A∈coNPA \in \mathsf{coNP}.

coNP⊆NP\mathsf{coNP} \subseteq \mathsf{NP}: sea A∈coNPA \in \mathsf{coNP}. Entonces A‾∈NP\overline{A} \in \mathsf{NP}, y por lo anterior A‾∈coNP\overline{A} \in \mathsf{coNP}, es decir, A∈NPA \in \mathsf{NP}. ∎

Es la respuesta a la pregunta de repaso 5: si alguien demuestra que 3-SAT está en coNP, entonces NP=coNP\mathsf{NP} = \mathsf{coNP}, y toda fórmula insatisfacible tendría una demostración corta de que lo es.

Por qué se cree que NP≠coNP\mathsf{NP} \neq \mathsf{coNP}. Porque nadie ha encontrado esos certificados, y se han buscado mucho: un sistema de demostración en el que toda tautología tenga una demostración de longitud polinomial es un objetivo viejo de la lógica. Para los sistemas que se conocen bien hay familias de fórmulas cuyas demostraciones más cortas son exponenciales; una aparece en la última sección de este capítulo.

Las dos conjeturas están relacionadas en un solo sentido. Si P=NP\mathsf{P} = \mathsf{NP}, entonces NP=coNP\mathsf{NP} = \mathsf{coNP}, porque P es cerrada bajo complemento. Dicho al revés: si NP≠coNP\mathsf{NP} \neq \mathsf{coNP}, entonces P≠NP\mathsf{P} \neq \mathsf{NP}. La segunda conjetura es más fuerte que la primera.

Lo que se cree, entonces, es este dibujo, con las cuatro regiones no vacías:

        ┌──────────── NP ────────────┐
        │   SAT, 3-SAT, HAMPATH      │
        │         ┌──────────────────┼───────────── coNP ─┐
        │         │  factorización   │                    │
        │         │      ┌─── P ───┐ │   UNSAT, TAUTOLOGY │
        │         │      │  2-SAT  │ │                    │
        │         │      └─────────┘ │                    │
        └─────────┼──────────────────┘                    │
                  └───────────────────────────────────────┘

Solo se sabe que P está dentro de la intersección. Todo lo demás del dibujo es conjetura.

Más allá. NP es “existe un certificado” y coNP es “para todo certificado”. Hay preguntas que necesitan los dos cuantificadores: “¿existe una fórmula más corta que φ\varphi y equivalente a ella?” pide que exista una fórmula tal que para toda asignación las dos coincidan. Las clases que se obtienen alternando una cantidad fija de cuantificadores forman la jerarquía polinomial, con NP y coNP en el primer nivel. No la estudiamos. La semana próxima veremos qué pasa cuando la cantidad de alternancias no tiene tope: las fórmulas booleanas cuantificadas, y la clase PSPACE.

Qué pasaría si P = NP

La pregunta lleva abierta desde 1971 y la mayoría de quienes trabajan en el área cree que P≠NP\mathsf{P} \neq \mathsf{NP}. No hay demostración en ningún sentido. Conviene saber qué diría cada respuesta, sin exagerar ninguna.

Si P=NP\mathsf{P} = \mathsf{NP}:

  • Todo problema de NP tendría un algoritmo polinomial: SAT, coloreo, horarios, rutas. Y no solo la versión de decisión. Con un algoritmo para SAT se encuentra una asignación preguntando variable por variable: se fija x1x_1 en verdadero y se pregunta si la fórmula sigue siendo satisfacible; si no, se fija en falso; y se sigue con x2x_2. Son nn preguntas.
  • NP=coNP\mathsf{NP} = \mathsf{coNP}, y la jerarquía polinomial entera sería igual a P.
  • Encontrar demostraciones sería tan fácil como revisarlas. “¿Tiene este enunciado una demostración de a lo sumo mm símbolos?” está en NP, con la demostración como certificado y mm escrito en unario, para que el certificado tenga longitud polinomial en la entrada.
  • La criptografía de clave pública que se usa hoy no sería segura. Romper un cifrado es, en esencia, un problema de NP: la clave es un certificado que se comprueba rápido.

Lo que P=NP\mathsf{P} = \mathsf{NP} no diría:

  • Que los algoritmos sean prácticos. Un algoritmo de tiempo n100n^{100} es polinomial. Y una demostración podría mostrar que el algoritmo existe sin decir cuál es.
  • Nada sobre lo indecidible. El problema de la parada seguiría sin tener algoritmo. Tampoco diría que P=PSPACE\mathsf{P} = \mathsf{PSPACE}.

Si se demostrara que P≠NP\mathsf{P} \neq \mathsf{NP}:

  • Ningún problema NP-completo tendría un algoritmo polinomial. Es lo que ya se supone al diseñar: en la práctica cambiaría poco.
  • No bastaría para la criptografía. Dice que cada algoritmo falla en algunas entradas, en el peor caso. Un cifrado necesita que casi todas las claves sean difíciles de romper, y eso es una afirmación sobre el caso típico, que no se sigue de la otra.
  • No diría que los solucionadores SAT sean inútiles: siguen resolviendo las instancias que resuelven.
  • Existirían problemas intermedios. Un teorema de Ladner dice que, si P≠NP\mathsf{P} \neq \mathsf{NP}, hay lenguajes de NP que no están en P y tampoco son NP-completos.

Lo que una demostración traería, en cualquiera de los dos sentidos, es una técnica nueva. Las que conocemos no alcanzan, y en la semana 15 veremos una razón precisa: la diagonalización, que resolvió el problema de la parada, no puede resolver este.

Los solucionadores SAT en la práctica

Queda una aparente contradicción. SAT es NP-completo, y en este capítulo le dimos a minisat fórmulas de decenas de miles de cláusulas que resolvió al instante.

NP-completo es una afirmación sobre el peor caso: no se conoce un algoritmo que sea rápido con todas las fórmulas. No dice nada de una fórmula en particular. Las del tableau son fáciles, y se ve en lo que informa el solucionador. Esta es la fórmula de la máquina de ejemplo con una entrada de 10 símbolos y t=20t = 20, que tiene 69 206 variables y 407 999 cláusulas en un archivo de 5,9 MB:

$ build/tableau_cnf machines/contains_11.tm 0000000110 20 > build/big.cnf
$ minisat build/big.cnf build/big.res
...
restarts              : 1
conflicts             : 1              (32 /sec)
decisions             : 41             (0.00 % random) (1313 /sec)
propagations          : 71470          (2289018 /sec)
...
SATISFIABLE

Una decisión es una variable a la que el solucionador le da un valor por probar. Un conflicto es una vez que tuvo que volver atrás. Aquí decidió 41 veces y se equivocó una. Todo lo demás, 71 470 valores, salió por propagación: cláusulas en las que todos los literales menos uno ya eran falsos, y que obligan al que queda. La fórmula del tableau está hecha de implicaciones cortas, y fijada la primera fila casi todo se sigue solo. Las cifras entre paréntesis son velocidades y cambian de una corrida a otra; las cuentas no.

El peor caso existe, y no hace falta una fórmula grande. El principio del palomar dice que n+1n + 1 palomas no caben en nn casillas sin compartir alguna. Escrito como fórmula, con una variable por paloma y casilla, es insatisfacible, y el solucionador tiene que demostrarlo:

$ build/pigeonhole 9 > build/php.cnf
$ minisat build/php.cnf build/php.res
...
conflicts             : 551941         (231206 /sec)
decisions             : 669045         (0.00 % random) (280260 /sec)
...
UNSATISFIABLE
Casillas nn Variables Cláusulas Conflictos
6 42 133 1206
7 56 204 10 495
8 72 297 76 178
9 90 415 551 941

Son corridas del minisat del entorno del curso; otra versión puede dar otros números. Cada casilla más multiplica los conflictos por más de 7. Con 90 variables y 415 cláusulas, medio millón de conflictos; con 69 206 variables y 407 999 cláusulas, uno. El tamaño de una fórmula dice poco de su dificultad.

Y esta familia no es mala suerte de un programa. Los solucionadores de este tipo, cuando responden UNSATISFIABLE, han construido una demostración en un sistema llamado resolución, y está demostrado que toda demostración por resolución del principio del palomar es exponencial. Es un caso concreto de lo que NP≠coNP\mathsf{NP} \neq \mathsf{coNP} afirma en general: fórmulas insatisfacibles sin demostración corta.

En la práctica. Que un problema sea NP-completo no cierra la conversación: la cambia. Reducir el problema a SAT y probar un solucionador es hoy una técnica normal de ingeniería, en verificación de circuitos, en planificación, en la resolución de dependencias de paquetes. Funciona porque las instancias que salen de problemas reales tienen estructura, como las del tableau. Lo que la teoría dice es qué no se puede prometer: que funcione siempre.

El código de la semana

code/week-13/
├── ntm.h                 struct Ntm, el formato .tm con varias líneas por par, configuraciones y pasos
├── tableau.h             las celdas, las filas, las ventanas legales y la comprobación de un tableau
├── cnf.h                 fórmulas en CNF: DIMACS, fuerza bruta y la llamada a minisat
├── cook_levin.h          la fórmula del tableau, grupo por grupo, y el paso de la asignación al tableau
├── three_sat.h           de CNF a 3-SAT
├── hampath.h             de 3-SAT a HAMPATH, el camino de una asignación y la búsqueda
├── random_ntm.h          máquinas pequeñas al azar, para las pruebas
├── run_ntm.cpp           el árbol de ejecuciones de una máquina, por niveles
├── windows.cpp           las ventanas legales de una máquina
├── tableau_cnf.cpp       la reducción: máquina, entrada y lado; sale la fórmula en DIMACS
├── decode_tableau.cpp    del resultado de minisat al tableau
├── three_sat.cpp         de una fórmula en DIMACS a una de 3-SAT
├── hampath.cpp           de una fórmula al grafo, y la búsqueda del camino
├── pigeonhole.cpp        el principio del palomar como fórmula
├── machines/             las máquinas del capítulo, en formato .tm
├── formulas/             las fórmulas pequeñas del capítulo, en DIMACS
├── errors/               tres descripciones que no son una máquina de Turing
├── test_ntm.cpp          el simulador y los lenguajes de las máquinas
├── test_tableau.cpp      las ventanas legales y el lema de las ventanas
├── test_cook_levin.cpp   la fórmula es satisfacible exactamente cuando la máquina acepta
├── test_three_sat.cpp    la reducción a 3-SAT conserva la respuesta
├── test_hampath.cpp      la reducción a HAMPATH, en las dos direcciones
└── lab/cook_levin/       el laboratorio

make compila todo, y make test corre las pruebas con ASan y UBSan. Necesitan minisat, que está en el entorno del curso.

$ make test
test_ntm: ok (5 máquinas, 511 cadenas)
test_tableau: ok (el lema de las ventanas con 5358 filas)
test_cook_levin: ok (262 fórmulas, 64 satisfacibles)
test_three_sat: ok (400 fórmulas al azar, 300 satisfacibles)
test_hampath: ok (210 fórmulas, 155 satisfacibles)
Todas las pruebas pasaron.

Cada prueba comprueba una afirmación de este capítulo.

  • test_ntm compara cada máquina de machines/ con una función de C++ que decide el mismo lenguaje, sobre las 511 cadenas binarias de longitud a lo sumo 8.
  • test_tableau comprueba que la tabla de las cuatro formas da exactamente las ventanas que aparecen en pasos de verdad, las propiedades (P1) a (P4) y el lema de las ventanas, por fuerza bruta.
  • test_cook_levin es el teorema, ejecutado. Para cada máquina, entrada y lado, compara lo que responde minisat con un recorrido completo del árbol de ejecuciones, rama por rama. Cuando la fórmula es satisfacible, decodifica el tableau y comprueba que es una ejecución que acepta. También comprueba que las cantidades de variables y de cláusulas son las de las cuentas de la sección Cuánto mide, y que pasar la fórmula a 3-SAT no cambia la respuesta. De las 262 fórmulas, 144 salen de 36 máquinas generadas al azar.
  • test_three_sat compara la fórmula original, resuelta por fuerza bruta, con la de 3-SAT, resuelta con minisat.
  • test_hampath comprueba el tamaño del grafo y las dos direcciones de la reducción.

Las máquinas de machines/ son:

Archivo Qué hace Ventanas legales
contains_11.tm Acepta las cadenas con 11\mathtt{11}. No determinista 193
contains_01_back.tm Acepta las cadenas con 01\mathtt{01}: marca un 1\mathtt{1} y retrocede. No determinista 453
left_end_accept.tm Acepta las que empiezan con 0\mathtt{0}, con un movimiento L\mathrm{L} en la primera celda 355
loop.tm No se detiene nunca 189
wait.tm Acepta todo, cuando quiera: tiene ramas que no terminan 282
zeros_ones.tm La máquina determinista de {0n1n}\{\mathtt{0}^n\mathtt{1}^n\} de la semana 7 1109

Para experimentar, prueben left_end_accept.tm con la entrada 0 y t=5t = 5: en el tableau, el estado no cambia de columna entre las filas 1 y 2. Es la tercera línea de la forma 1. Después prueben loop.tm con cualquier entrada: la fórmula es insatisfacible con todo tt, y la única razón es el grupo 4.

El laboratorio

En lab/cook_levin está el enunciado, un esqueleto, el verificador, un decodificador y los casos. El problema es escribir la reducción: la entrada es una máquina, una cadena y el lado del tableau, y la salida es la fórmula en DIMACS.

cd lab/cook_levin
make        # compila solution.cpp y decode.cpp
make test   # corre el juez con todos los casos

El esqueleto trae la lectura, la numeración de las variables y el grupo 1. Ustedes escriben los otros tres: la primera fila, las ventanas y la aceptación. solution.cpp se escribe sin incluir los encabezados de esta carpeta, que ya tienen todo resuelto; pueden leerlos cuanto quieran.

Una fórmula no es única, y el juez no compara textos. El verificador corre minisat con su fórmula y mira tres cosas: que la respuesta sea la esperada; que la fórmula admita los tableaux que son ejecuciones que aceptan; y que rechace varios tableaux que no lo son, cada uno elegido para que falle un solo grupo. Así una fórmula a la que le falta un grupo no pasa por casualidad. Después del juez, el enunciado pide decodificar el tableau, compararlo con su simulador de la semana 7 y contar variables y cláusulas para t=5t = 5, 10 y 20.

Resumen

  • A≤pBA \leq_p B si una función de tiempo polinomial traduce AA en BB sin cambiar la respuesta. BB es NP-difícil si todo NP se reduce a él, y NP-completo si además está en NP. Las dos partes se demuestran.
  • Si un problema NP-completo está en P, entonces P=NP\mathsf{P} = \mathsf{NP}. Para mostrar que un problema nuevo es NP-completo se reduce desde uno conocido hacia el nuevo.
  • El primer problema NP-completo no puede salir de una reducción desde otro. Cook-Levin: SAT es NP-completo. La demostración reduce todos los lenguajes de NP a la vez, usando solo que cada uno tiene una máquina no determinista de tiempo nkn^k.
  • El tableau es una tabla con una configuración por fila, entre dos columnas de #\mathtt{\#}, de lado t=nk+4t = n^k + 4. NN acepta ww si y solo si existe un tableau que acepta ww.
  • La fórmula tiene una variable xi,j,sx_{i,j,s} por celda y símbolo, y cuatro grupos: cada celda tiene exactamente un símbolo; la fila 1 es la configuración inicial con ww; cada ventana de 2×32 \times 3 es legal; alguna celda contiene qacceptq_{\text{accept}}.
  • Una ventana es legal si aparece en algún paso de la máquina. Bastan las ventanas porque un paso solo cambia las tres columnas del cabezal, y la ventana que tiene el estado en el centro las ve a las tres. Es la localidad de las historias de cómputo de la semana 10.
  • La fórmula tiene O(n2k)O(n^{2k}) variables y literales, y se escribe en tiempo polinomial sin ejecutar la máquina. No simula: describe cómo se ve una ejecución que acepta.
  • Una reducción conserva que la fórmula sea satisfacible, no que sea equivalente. Con variables nuevas se pasa a CNF sin crecimiento exponencial, y se parten las cláusulas largas en cláusulas de tres literales: 3-SAT es NP-completo.
  • Con eso, las reducciones de Algoritmos quedan completas hasta el fondo, y todos los problemas NP-completos son reducibles entre sí: basta que uno esté en P para que todos lo estén.
  • HAMPATH es NP-completo: un rombo por variable, que se recorre en uno de dos sentidos, y un nodo por cláusula que se visita con un desvío.
  • 2-SAT está en P, por las componentes fuertemente conexas del grafo de implicaciones. El borde entre fácil y difícil pasa entre 2 y 3.
  • coNP tiene los lenguajes cuyo complemento está en NP: UNSAT, TAUTOLOGY. P⊆NP∩coNP\mathsf{P} \subseteq \mathsf{NP} \cap \mathsf{coNP}. Si un problema NP-completo está en coNP, entonces NP=coNP\mathsf{NP} = \mathsf{coNP}. Se cree que son distintas, y eso implicaría P≠NP\mathsf{P} \neq \mathsf{NP}.
  • P=NP\mathsf{P} = \mathsf{NP} daría algoritmos polinomiales para todo NP, no necesariamente prácticos. P≠NP\mathsf{P} \neq \mathsf{NP} no bastaría para la criptografía. Las dos preguntas siguen abiertas.
  • NP-completo habla del peor caso. Un solucionador SAT resuelve fórmulas enormes con estructura, y se atasca con fórmulas pequeñas como el principio del palomar.

Ejercicios

  1. Para la máquina de machines/contains_11.tm, escriban a mano el tableau de lado 6 que acepta 11\mathtt{11}. Después digan cuál es el menor lado con el que existe un tableau que acepta 0011\mathtt{0011}, y comprueben las dos respuestas con tableau_cnf, minisat y decode_tableau.
  2. Para el movimiento (q0,0,R)∈δ(q0,0)(q_0, \mathtt{0}, \mathrm{R}) \in \delta(q_0, \mathtt{0}) de la misma máquina, den dos ventanas legales de formas distintas y dos ilegales, y expliquen por qué cada una lo es. Comprueben con build/windows. Es la pregunta de repaso 2.
  3. La máquina machines/left_end_accept.tm tiene 355 ventanas legales y ∣C∣=9|C| = 9. Sin correr el programa, calculen cuántas variables y cuántas cláusulas tiene la fórmula de tableau_cnf con t=6t = 6. Comprueben con --cuenta.
  4. En la demostración del lema de las ventanas, ¿dónde se usa que la fila de arriba tiene un solo estado? Den una fila de arriba con dos estados y una fila de abajo tales que todas las ventanas entre ellas sean legales para contains_11.tm, y expliquen por qué eso no contradice el lema.
  5. Supongan que se quita de la definición de ventana legal el caso de la aceptación, de modo que una configuración en qacceptq_{\text{accept}} no tiene fila siguiente. ¿Para qué entradas sigue siendo satisfacible la fórmula? Propongan otro cambio que arregle la demostración sin repetir la configuración, y digan qué grupo de cláusulas habría que modificar.
  6. La cláusula (x1∨¬x2∨x3∨x4∨¬x5∨x6)(x_1 \lor \lnot x_2 \lor x_3 \lor x_4 \lor \lnot x_5 \lor x_6) se parte en una cadena. Escriban la cadena. Para la asignación que hace verdadero solo a x4x_4, den los valores de las variables nuevas que cumplen la cadena, y digan si son los únicos.
  7. Demuestren que la construcción de las variables nuevas zz sigue siendo correcta si se quita la cláusula “a lo sumo una zz es verdadera”, que nunca pusimos. Después demuestren que deja de serlo si se quita la cláusula larga (z1∨⋯∨zL)(z_1 \lor \cdots \lor z_L): ¿qué tableaux admite entonces la fórmula?
  8. Demuestren que SAT≤pHAMPATH\mathrm{SAT} \leq_p \mathrm{HAMPATH} sin hacer ninguna construcción nueva. ¿Qué propiedad de las reducciones usan? ¿Vale también HAMPATH≤pSAT\mathrm{HAMPATH} \leq_p \mathrm{SAT}? ¿Por qué?
  9. Para la fórmula (x1∨x2)∧(¬x1∨¬x2)(x_1 \lor x_2) \land (\lnot x_1 \lor \lnot x_2), tratada como una fórmula en CNF con cláusulas de dos literales, dibujen el grafo de la reducción a HAMPATH y den un camino hamiltoniano para cada asignación que la cumple. Comprueben el tamaño del grafo con build/hampath.
  10. Dibujen el grafo de implicaciones de (x∨y)∧(¬y∨z)∧(¬x∨¬z)∧(¬x∨y)(x \lor y) \land (\lnot y \lor z) \land (\lnot x \lor \lnot z) \land (\lnot x \lor y), encuentren sus componentes fuertemente conexas y den una asignación con el criterio del capítulo. Después agreguen una cláusula de dos literales que la vuelva insatisfacible y muestren el ciclo.
  11. Demuestren que coNP\mathsf{coNP} es cerrada bajo reducciones: si A≤pBA \leq_p B y B∈coNPB \in \mathsf{coNP}, entonces A∈coNPA \in \mathsf{coNP}. Con eso, demuestren que TAUTOLOGY restringido a fórmulas en CNF está en P. ¿Por qué eso no dice nada sobre SAT en CNF?
  12. Supongan que tienen una función sat(f) de tiempo polinomial que solo responde sí o no. Escriban, en pseudocódigo, un algoritmo de tiempo polinomial que encuentre una asignación de una fórmula satisfacible. ¿Cuántas veces llama a sat? ¿Qué cambia si sat solo acepta fórmulas de 3-SAT?
  13. Para programar. Agreguen a tableau_cnf una opción que escriba el grupo 3 por la segunda manera, con una cláusula por ventana ilegal, y comparen los tamaños con t=4t = 4 y t=5t = 5 para machines/loop.tm. Comprueben con minisat que las dos fórmulas responden lo mismo, y con decode_tableau que el tableau que sale es una ejecución de la máquina.
  14. Para programar. Escriban un programa que reciba una fórmula de 2-SAT en DIMACS y decida si es satisfacible con el criterio de las componentes fuertemente conexas. Compárenlo con minisat sobre fórmulas al azar de 50 variables. Después pásenle la salida de three_sat para una fórmula cualquiera y expliquen por qué su programa no puede usarse con ella.