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

Apuntes · Capítulo 12Complejidad

Tiempo: P y NP

Tiempo: P y NP

Las semanas 9 a 11 trazaron una frontera: de un lado los lenguajes decidibles, del otro los que ninguna máquina de Turing decide, como ATMA_{\mathrm{TM}} y el problema de la parada. Esa frontera no dice nada sobre el costo. Para ella da lo mismo un problema que se decide en un segundo que uno que necesita más pasos que átomos tiene el universo: los dos son “decidibles”. Esta semana empieza la cuarta parte del curso, la complejidad, que mira dentro de lo decidible y pregunta cuánto cuesta.

En Análisis y Diseño de Algoritmos ya trabajaron con esa pregunta. Contaron operaciones, escribieron O(nlog⁡n)O(n \log n), y en las últimas semanas conocieron P, NP y los problemas NP-completos. Pero todo eso se apoyaba en una idea informal de “algoritmo” y de “operación”. ¿Una suma de dos números de mil dígitos es una operación? ¿Leer una casilla de un arreglo lo es, aunque el arreglo tenga 2602^{60} casillas? Para comparar algoritmos esas preguntas casi nunca importan. Para demostrar que un problema no tiene algoritmo rápido, o que todos los problemas de una clase se reducen a uno solo, importan: hay que razonar sobre todos los algoritmos posibles a la vez, y eso exige una definición. Ya la tenemos, desde la semana 7: la máquina de Turing.

Esta semana redefine P y NP sobre máquinas de Turing, con cuidado.

  • En la sesión A se define el tiempo de una máquina, se cuenta de verdad cuántos pasos dan tres máquinas para un mismo lenguaje, y se demuestra que la clase P no depende de los detalles del modelo. También se mira un detalle que en Algoritmos pasó rápido y que aquí es central: cómo se escribe la entrada.
  • En la sesión B se define NP de dos maneras, con verificadores y con máquinas no deterministas, y se demuestra que las dos definiciones dan la misma clase. Se ubica a NP entre P y EXPTIME, y aparece coNP.

No vamos a repetir el catálogo de reducciones de Algoritmos. Las reducciones vuelven la semana 13, cuando se demuestre el teorema que allá solo se enunció: que SAT es NP-completo.

Ruta de lectura.

Antes de clase (15–20 minutos): la introducción, De «¿se puede?» a «¿cuánto cuesta?» y El tiempo de una máquina. Antes de la sesión B, Encontrar frente a comprobar. Con eso llegan con la definición de tiempo y con la idea de certificado.

En clase: Sesión A, de El tiempo de una máquina a El no determinismo parece costar caro. Sesión B, de Encontrar frente a comprobar a coNP: el lado del no.

Después de clase: el Resumen y los Ejercicios, para repasar. Antes del laboratorio, Verificadores y la clase NP, Cinco problemas de NP y sus certificados y El código de la semana. Para ampliar, las lecturas de apoyo del recuadro siguiente.

Lectura. Sipser, sec. 7.1 (Measuring Complexity), 7.2 (The Class P) y 7.3 (The Class NP). Barak, capítulo 13 (Modeling running time) y la primera parte del capítulo 15 (NP, NP completeness, and the Cook-Levin Theorem). Son apoyo: estos apuntes se pueden estudiar solos.

Código. Los programas de este capítulo están en code/week-12. 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/verifiers.

De «¿se puede?» a «¿cuánto cuesta?»

Hasta la semana pasada, una máquina podía hacer tres cosas con una entrada: aceptarla, rechazarla o no detenerse nunca. Toda la parte de computabilidad giró alrededor de la tercera posibilidad.

En esta parte del curso esa posibilidad desaparece. Todas las máquinas de las semanas 12 a 15 son decididores: se detienen con todas las entradas. Y todos los lenguajes de los que hablaremos son decidibles. La pregunta ya no es si la máquina termina, sino después de cuántos pasos.

Conviene tener a la vista qué cambia y qué no respecto de lo que hicieron en Algoritmos.

En Algoritmos Aquí
Qué se mide Operaciones de un algoritmo en pseudocódigo Pasos de una máquina de Turing
Qué se clasifica Algoritmos: mergesort es O(nlog⁡n)O(n \log n) Lenguajes: en qué clase está un problema
Tamaño de la entrada Lo que conviene: nn elementos, VV vértices La longitud de la cadena que codifica la entrada
P y NP Presentadas sobre algoritmos, sin modelo fijo Definidas sobre máquinas, y demostradas robustas

La segunda fila es el cambio de punto de vista más importante. En Algoritmos el objeto de estudio era un algoritmo, y la pregunta era cuánto tarda. Aquí el objeto es un problema, escrito como lenguaje, y la pregunta es cuánto tarda el mejor algoritmo posible para él. Decir que un lenguaje está en una clase es decir que existe una máquina que lo decide dentro de cierto costo. Decir que no está es afirmar algo sobre todas las máquinas.

El tiempo de una máquina

Un paso de una máquina de Turing es una aplicación de su función de transición δ\delta: leer el símbolo bajo el cabezal, escribir, mover el cabezal y cambiar de estado. Contar pasos no tiene ninguna ambigüedad, y esa es la ventaja de tener un modelo fijo.

La cantidad de pasos depende de la entrada. Para resumirla en una función se hace lo mismo que en Algoritmos: se agrupan las entradas por su longitud y se toma el peor caso.

Definición. Sea MM una máquina de Turing determinista que se detiene con todas las entradas. El tiempo de MM, o su complejidad en tiempo (time complexity), es la función f:N→Nf : \mathbb{N} \to \mathbb{N} donde

f(n)=el maˊximo nuˊmero de pasos que da M con una entrada de longitud n.f(n) = \text{el máximo número de pasos que da } M \text{ con una entrada de longitud } n.

Si el tiempo de MM es f(n)f(n), decimos que MM corre en tiempo f(n)f(n), o que es una máquina de tiempo f(n)f(n).

Tres cosas de esta definición que vale la pena leer despacio.

  • nn es la longitud de la cadena de entrada, en símbolos. No es “el número nn” que la entrada pueda representar, ni la cantidad de vértices de un grafo. Si la entrada es ⟨G⟩\langle G \rangle, nn es cuántos símbolos tiene esa codificación. Volveremos sobre esto, porque es la fuente del error más frecuente de la semana.
  • Es el peor caso. Para cada longitud hay ∣Σ∣n|\Sigma|^n entradas, y f(n)f(n) es el máximo sobre todas. Una máquina que casi siempre termina rápido y con una sola entrada de cada longitud tarda muchísimo tiene un tiempo grande.
  • Solo tiene sentido para decididores. Si MM no se detiene con alguna entrada, el máximo no existe.

La función exacta suele ser incómoda: depende de detalles de la máquina que no dicen nada del problema. Se usa la notación asintótica de Algoritmos. Recuerden: f(n)=O(g(n))f(n) = O(g(n)) si existen constantes c>0c > 0 y n0n_0 tales que f(n)≤c⋅g(n)f(n) \leq c \cdot g(n) para todo n≥n0n \geq n_0. La OO es una cota superior que ignora las constantes y los valores pequeños de nn. También usaremos 2O(g(n))2^{O(g(n))}, que significa “a lo sumo 2c⋅g(n)2^{c \cdot g(n)} para alguna constante cc”: aquí la constante está en el exponente, y no se puede sacar.

Con eso se pueden clasificar los lenguajes.

Definición. Sea t:N→Nt : \mathbb{N} \to \mathbb{N} una función. La clase TIME(t(n))\mathsf{TIME}(t(n)) es el conjunto de los lenguajes que decide alguna máquina de Turing determinista, de una cinta, que corre en tiempo O(t(n))O(t(n)).

TIME(t(n))={ L:alguna maˊquina determinista de una cinta decide L en tiempo O(t(n)) }\mathsf{TIME}(t(n)) = \{\, L : \text{alguna máquina determinista de una cinta decide } L \text{ en tiempo } O(t(n)) \,\}

Por ejemplo, TIME(n2)\mathsf{TIME}(n^2) tiene a todos los lenguajes que se pueden decidir con una cantidad cuadrática de pasos. Como n=O(n2)n = O(n^2), también tiene a los que se deciden en tiempo lineal: las clases crecen con la función, TIME(n)⊆TIME(n2)⊆TIME(n3)\mathsf{TIME}(n) \subseteq \mathsf{TIME}(n^2) \subseteq \mathsf{TIME}(n^3).

Idea clave. TIME(t(n))\mathsf{TIME}(t(n)) es una clase de lenguajes, no de máquinas. Para demostrar que L∈TIME(t(n))L \in \mathsf{TIME}(t(n)) basta exhibir una máquina. Para demostrar que L∉TIME(t(n))L \notin \mathsf{TIME}(t(n)) hay que descartar todas, y eso es mucho más difícil: casi todas las preguntas abiertas de esta parte del curso son de ese tipo.

La definición fija el modelo: determinista y de una cinta. Las dos secciones que siguen muestran por qué hay que fijarlo, y después por qué, para lo que nos interesa, no importa tanto.

Tres máquinas para 0ᵏ1ᵏ

Tomemos un lenguaje que conocen desde la primera semana:

A={ 0k1k:k≥0 }A = \{\, \mathtt{0}^k\mathtt{1}^k : k \geq 0 \,\}

No es regular, así que ningún DFA lo reconoce. Una máquina de Turing sí lo decide, y la de la semana 7 lo hace. ¿En cuánto tiempo? Vamos a ver tres máquinas, cada una más rápida que la anterior, y a contar sus pasos con un simulador.

Antes, un intento que no funciona, para tener claro qué es lo difícil. Lo más rápido que puede hacer una máquina es leer la entrada una sola vez, de izquierda a derecha: n+1n + 1 pasos, contando el que lee el primer blanco. El archivo errors/zeros_ones_one_pass.tm hace eso, recordando en el estado solo si ya empezaron los unos:

$ build/run_tm errors/zeros_ones_one_pass.tm 001
w = 001
  acepta en 4 pasos

Acepta 001\mathtt{001}, que no está en AA. Lo que comprueba es la forma 0∗1∗\mathtt{0}^*\mathtt{1}^*, que es un lenguaje regular. Una máquina que solo avanza y nunca escribe algo que vuelva a leer es un autómata finito, y un autómata finito no puede comparar dos cantidades sin tope. Para decidir AA hay que volver sobre la cinta.

La máquina cuadrática

La máquina de la semana 7 empareja cada 0\mathtt{0} con un 1\mathtt{1}. Descripción de implementación:

M1 = "Con la entrada w:
  1. Si el cabezal está sobre un 0, cambiarlo por X. Si está sobre una Y, ir al paso 4.
     Si está sobre un blanco, aceptar. Si está sobre un 1, rechazar.
  2. Avanzar a la derecha, saltando ceros y letras Y, hasta el primer 1. Cambiarlo por Y.
     Si no hay ningún 1, rechazar.
  3. Retroceder hasta la X más cercana, quedar a su derecha, y volver al paso 1.
  4. Avanzar a la derecha saltando letras Y. Si se llega al blanco, aceptar.
     Si aparece otro símbolo, rechazar."

Y su descripción formal, que es el archivo machines/zeros_ones_quadratic.tm. Es la misma máquina que sirve de ejemplo en code/formats.md. Las casillas vacías llevan a qrejectq_{\text{reject}}.

δ\delta 0\mathtt{0} 1\mathtt{1} X\mathtt{X} Y\mathtt{Y} ⊔\sqcup
q0q_0 (q1,X,R)(q_1, \mathtt{X}, \mathrm{R}) (q3,Y,R)(q_3, \mathtt{Y}, \mathrm{R}) (qaccept,⊔,R)(q_{\text{accept}}, \sqcup, \mathrm{R})
q1q_1 (q1,0,R)(q_1, \mathtt{0}, \mathrm{R}) (q2,Y,L)(q_2, \mathtt{Y}, \mathrm{L}) (q1,Y,R)(q_1, \mathtt{Y}, \mathrm{R})
q2q_2 (q2,0,L)(q_2, \mathtt{0}, \mathrm{L}) (q0,X,R)(q_0, \mathtt{X}, \mathrm{R}) (q2,Y,L)(q_2, \mathtt{Y}, \mathrm{L})
q3q_3 (q3,Y,R)(q_3, \mathtt{Y}, \mathrm{R}) (qaccept,⊔,R)(q_{\text{accept}}, \sqcup, \mathrm{R})

El programa run_tm ejecuta una máquina en formato .tm y cuenta sus pasos. Con --watch '*' imprime cada configuración u q vu\,q\,v, con el estado entre corchetes:

$ build/run_tm machines/zeros_ones_quadratic.tm --watch '*' 0011
w = 0011
   [q0] 0011
  X [q1] 011
  X0 [q1] 11
  X [q2] 0Y1
   [q2] X0Y1
  X [q0] 0Y1
  XX [q1] Y1
  XXY [q1] 1
  XX [q2] YY
  X [q2] XYY
  XX [q0] YY
  XXY [q3] Y
  XXYY [q3] _
  XXYY_ [q_accept] _
  acepta en 13 pasos

Son 14 configuraciones y 13 pasos: un paso lleva de cada configuración a la siguiente. Se ven las dos idas y vueltas, una por cada 0\mathtt{0}, y el recorrido final sobre las Y\mathtt{Y}.

¿Cuántos pasos da con 0k1k\mathtt{0}^k\mathtt{1}^k? Se puede contar a mano. Hay kk rondas, una por cada 0\mathtt{0}. En cada ronda:

  • q0q_0 lee un 0\mathtt{0} y lo marca: 1 paso.
  • q1q_1 avanza sobre los k−1k - 1 símbolos que hay entre esa X y el primer 1\mathtt{1} sin marcar (son ceros y letras Y, y siempre suman k−1k - 1): k−1k - 1 pasos. Después lee el 1\mathtt{1} y lo marca: 1 paso.
  • q2q_2 retrocede sobre los mismos k−1k - 1 símbolos, y lee la X: k−1k - 1 pasos y 1 paso más.

Cada ronda cuesta 2k+12k + 1 pasos, y las kk rondas, 2k2+k2k^2 + k. Al final, q0q_0 lee una Y (1 paso), q3q_3 recorre las otras k−1k - 1 (otros k−1k - 1 pasos) y lee el blanco (1 paso): k+1k + 1 pasos más. En total:

2k2+k+(k+1)=2k2+2k+1=n22+n+1,con n=2k.2k^2 + k + (k + 1) = 2k^2 + 2k + 1 = \frac{n^2}{2} + n + 1, \qquad \text{con } n = 2k.

Para k=2k = 2 da 8+4+1=138 + 4 + 1 = 13, lo que imprimió run_tm. Las pruebas de la semana comprueban la fórmula para todos los kk hasta 300.

Esa cuenta es para una entrada particular de cada longitud. El tiempo de la máquina es el máximo sobre todas las entradas, así que falta una cota que valga siempre.

Afirmación. M1M_1 corre en tiempo O(n2)O(n^2).

Demostración. Por conteo directo. Sea ww una entrada de longitud nn. El cabezal nunca pasa de la celda n+1n + 1, porque ningún estado avanza después de leer un blanco. Cada ronda (pasos 1 a 3) cambia un 0\mathtt{0} por una X, y nunca se borra una X: hay a lo sumo nn rondas. En una ronda, q1q_1 solo avanza y q2q_2 solo retrocede, así que la ronda da a lo sumo 1+(n+1)+(n+1)1 + (n + 1) + (n + 1) pasos. El paso 4 solo avanza: a lo sumo n+1n + 1 pasos. En total, a lo sumo n(2n+3)+n+2=O(n2)n(2n + 3) + n + 2 = O(n^2) pasos. ∎

Y la cuenta de 0k1k\mathtt{0}^k\mathtt{1}^k muestra que la cota no se puede mejorar para esta máquina: con esas entradas da más de n2/2n^2/2 pasos. El tiempo de M1M_1 es cuadrático, ni más ni menos. Con eso, A∈TIME(n2)A \in \mathsf{TIME}(n^2).

Tachar uno de cada dos: O(n log n)

M1M_1 es lenta porque cada viaje de ida y vuelta, que cuesta nn pasos, elimina un solo 0\mathtt{0} y un solo 1\mathtt{1}. La segunda máquina hace que cada viaje elimine la mitad de los que quedan.

La idea es comparar las dos cantidades sin emparejar los símbolos uno por uno. Supongan que quedan zz ceros y uu unos sin tachar. Entonces:

z=usi y solo siz y u tienen la misma paridad, y ⌊z/2⌋=⌊u/2⌋.z = u \quad \text{si y solo si} \quad z \text{ y } u \text{ tienen la misma paridad, y } \lfloor z/2 \rfloor = \lfloor u/2 \rfloor.

Es cierto porque todo número se escribe como z=2⌊z/2⌋+(z mod 2)z = 2\lfloor z/2 \rfloor + (z \bmod 2): el cociente y el resto de dividir entre 2 determinan el número. La paridad se puede calcular con dos estados en una sola pasada, y pasar de zz a ⌊z/2⌋\lfloor z/2 \rfloor también: basta tachar un cero sí y uno no, empezando por el primero. Si había zz, quedan ⌊z/2⌋\lfloor z/2 \rfloor. Después se repite la pregunta con las mitades.

M2 = "Con la entrada w:
  1. Recorrer la cinta de izquierda a derecha. Si aparece un 0 después de un 1, rechazar.
     Durante el recorrido, tachar un 0 sí y uno no, empezando por el primero sin tachar,
     y lo mismo con los unos. Recordar en el estado la paridad de los ceros y la de
     los unos que estaban sin tachar.
  2. Si en el recorrido no había ningún símbolo sin tachar, aceptar.
  3. Si las dos paridades son distintas, rechazar.
  4. Volver al borde izquierdo y repetir desde el paso 1."

La descripción formal está en machines/zeros_ones_nlogn.tm. Tiene nueve estados además de los dos finales.

Estado Qué recuerda
q0q_0 Solo se usa en el primer paso: marca la primera celda con S\mathtt{S}, para reconocer después el borde izquierdo
n\mathit{n} Pasada en curso; todavía no vio ningún símbolo sin tachar
z1z_1, z2z_2 Está en los ceros: vio una cantidad impar (z1z_1), o par y mayor que cero (z2z_2)
ee\mathit{ee}, eo\mathit{eo}, oe\mathit{oe}, oo\mathit{oo} Está en los unos: la primera letra es la paridad de los ceros y la segunda la de los unos (e par, o impar)
back\mathit{back} Vuelve al borde izquierdo

La tabla completa, con X para un símbolo tachado. Las casillas vacías llevan a qrejectq_{\text{reject}}.

δ\delta 0\mathtt{0} 1\mathtt{1} X\mathtt{X} S\mathtt{S} ⊔\sqcup
q0q_0 (z1,S,R)(z_1, \mathtt{S}, \mathrm{R}) (qaccept,⊔,R)(q_{\text{accept}}, \sqcup, \mathrm{R})
n\mathit{n} (z1,X,R)(z_1, \mathtt{X}, \mathrm{R}) (eo,X,R)(\mathit{eo}, \mathtt{X}, \mathrm{R}) (n,X,R)(\mathit{n}, \mathtt{X}, \mathrm{R}) (qaccept,⊔,R)(q_{\text{accept}}, \sqcup, \mathrm{R})
z1z_1 (z2,0,R)(z_2, \mathtt{0}, \mathrm{R}) (oo,X,R)(\mathit{oo}, \mathtt{X}, \mathrm{R}) (z1,X,R)(z_1, \mathtt{X}, \mathrm{R})
z2z_2 (z1,X,R)(z_1, \mathtt{X}, \mathrm{R}) (eo,X,R)(\mathit{eo}, \mathtt{X}, \mathrm{R}) (z2,X,R)(z_2, \mathtt{X}, \mathrm{R}) (back,⊔,L)(\mathit{back}, \sqcup, \mathrm{L})
ee\mathit{ee} (eo,X,R)(\mathit{eo}, \mathtt{X}, \mathrm{R}) (ee,X,R)(\mathit{ee}, \mathtt{X}, \mathrm{R}) (back,⊔,L)(\mathit{back}, \sqcup, \mathrm{L})
eo\mathit{eo} (ee,1,R)(\mathit{ee}, \mathtt{1}, \mathrm{R}) (eo,X,R)(\mathit{eo}, \mathtt{X}, \mathrm{R})
oe\mathit{oe} (oo,X,R)(\mathit{oo}, \mathtt{X}, \mathrm{R}) (oe,X,R)(\mathit{oe}, \mathtt{X}, \mathrm{R})
oo\mathit{oo} (oe,1,R)(\mathit{oe}, \mathtt{1}, \mathrm{R}) (oo,X,R)(\mathit{oo}, \mathtt{X}, \mathrm{R}) (back,⊔,L)(\mathit{back}, \sqcup, \mathrm{L})
back\mathit{back} (back,0,L)(\mathit{back}, \mathtt{0}, \mathrm{L}) (back,1,L)(\mathit{back}, \mathtt{1}, \mathrm{L}) (back,X,L)(\mathit{back}, \mathtt{X}, \mathrm{L}) (n,S,R)(\mathit{n}, \mathtt{S}, \mathrm{R})

Cómo leerla. Un símbolo se tacha cuando es el primero, el tercero, el quinto de su grupo: es decir, cuando la paridad de los vistos antes era par. Por eso z2z_2 tacha el 0\mathtt{0} que lee y z1z_1 lo deja. El primer 0\mathtt{0} de la entrada es siempre el primero sin tachar, y en lugar de X recibe la marca S\mathtt{S}, que cumple dos funciones: cuenta como tachado y señala el borde. Al llegar al blanco, la máquina vuelve solo desde z2z_2, ee\mathit{ee} y oo\mathit{oo}, los estados donde las dos paridades coinciden; en los demás no hay transición y rechaza. Y en los estados de los unos no hay transición con 0\mathtt{0}: un cero después de un uno rechaza.

Con --watch n, run_tm imprime la configuración cada vez que la máquina entra al estado n\mathit{n}, es decir, al empezar cada pasada después de la primera. Con cinco ceros y cinco unos:

$ build/run_tm machines/zeros_ones_nlogn.tm --watch n 0000011111
w = 0000011111
  S [n] 0X0XX1X1X
  S [n] XX0XXXX1X
  S [n] XXXXXXXXX
  acepta en 71 pasos

Después de la primera pasada quedan 2 ceros y 2 unos sin tachar: ⌊5/2⌋=2\lfloor 5/2 \rfloor = 2. Después de la segunda, 1 y 1. Después de la tercera, ninguno, y la cuarta pasada no encuentra nada y acepta. Las paridades que la máquina vio en las tres pasadas fueron impar, par, impar: leídas al revés son 101\mathtt{101}, el número 5 en binario. La máquina compara, sin saberlo, la escritura en binario de la cantidad de ceros con la de unos, un bit por pasada, empezando por el menos significativo.

Animación de la máquina zeros_ones_nlogn.tm con la entrada 0000011111. Arriba está la cinta con el cabezal y el estado debajo; al centro, una tabla con una fila por pasada. Al comienzo la cinta tiene cinco ceros y cinco unos. Pasada 1: la máquina marca la primera celda con S, tacha con X el tercer y el quinto cero y el primer, tercer y quinto uno; llega al blanco habiendo visto 5 ceros y 5 unos, impar e impar, la cinta queda S0X0XX1X1X con 2 ceros y 2 unos sin tachar, y vuelve al borde izquierdo. Pasada 2: había 2 y 2, par y par; la cinta queda SXX0XXXX1X, con 1 y 1. Pasada 3: había 1 y 1, impar e impar; la cinta queda SXXXXXXXXX, sin nada. Pasada 4: no encuentra ningún símbolo sin tachar y acepta, en el paso 71 de 71.Animación de la máquina zeros_ones_nlogn.tm con la entrada 0000011111. Arriba está la cinta con el cabezal y el estado debajo; al centro, una tabla con una fila por pasada. Al comienzo la cinta tiene cinco ceros y cinco unos. Pasada 1: la máquina marca la primera celda con S, tacha con X el tercer y el quinto cero y el primer, tercer y quinto uno; llega al blanco habiendo visto 5 ceros y 5 unos, impar e impar, la cinta queda S0X0XX1X1X con 2 ceros y 2 unos sin tachar, y vuelve al borde izquierdo. Pasada 2: había 2 y 2, par y par; la cinta queda SXX0XXXX1X, con 1 y 1. Pasada 3: había 1 y 1, impar e impar; la cinta queda SXXXXXXXXX, sin nada. Pasada 4: no encuentra ningún símbolo sin tachar y acepta, en el paso 71 de 71.
Cada pasada cuesta unos 2n pasos y deja la mitad de los símbolos: de 5 quedan 2, 1 y 0. Por eso bastan unas log₂ n pasadas. Las paridades que ve, impar, par, impar, son los bits de 5 leídos desde el menos significativo.

Con cinco ceros y tres unos, la primera pasada ve dos cantidades impares y continúa. La segunda encuentra 2 ceros y 1 uno, y rechaza:

$ build/run_tm machines/zeros_ones_nlogn.tm --watch n 00000111
w = 00000111
  S [n] 0X0XX1X
  rechaza en 25 pasos

Afirmación. M2M_2 decide AA.

Demostración. Por inducción sobre la cantidad de símbolos sin tachar. Primero la forma: en la primera pasada todos los símbolos están sin tachar, así que cualquier 0\mathtt{0} que venga después de un 1\mathtt{1} se lee en un estado de los unos y la máquina rechaza. Si la entrada empieza con 1\mathtt{1}, q0q_0 rechaza en el primer paso, y es correcto: ninguna cadena de AA empieza con 1\mathtt{1}. Si la entrada pasa de ahí, es de la forma 0z1u\mathtt{0}^z\mathtt{1}^u, y tachar símbolos no cambia eso. Queda ver que, si al empezar una pasada hay zz ceros y uu unos sin tachar, la máquina termina aceptando si y solo si z=uz = u.

Caso base: z+u=0z + u = 0. La pasada no encuentra símbolos sin tachar, llega al blanco en el estado n\mathit{n} (o en q0q_0, si la entrada es ε\varepsilon) y acepta. Es correcto, porque z=u=0z = u = 0.

Paso inductivo: z+u>0z + u > 0. Si zz y uu tienen distinta paridad, la máquina rechaza al llegar al blanco, y es correcto porque z≠uz \neq u. Si tienen la misma paridad, la pasada deja ⌊z/2⌋\lfloor z/2 \rfloor ceros y ⌊u/2⌋\lfloor u/2 \rfloor unos, que suman menos que z+uz + u. Por hipótesis de inducción, desde ahí la máquina acepta si y solo si ⌊z/2⌋=⌊u/2⌋\lfloor z/2 \rfloor = \lfloor u/2 \rfloor, y con paridades iguales eso equivale a z=uz = u, por la equivalencia del comienzo de esta sección. ∎

Afirmación. M2M_2 corre en tiempo O(nlog⁡n)O(n \log n).

Demostración. Por conteo. Una pasada completa recorre la cinta hasta el primer blanco y vuelve: a lo sumo (n+1)+n=2n+1(n + 1) + n = 2n + 1 pasos. Falta contar las pasadas. Sea rr la mayor de las dos cantidades zz y uu de la entrada; r≤nr \leq n. Después de jj pasadas que tachan, de la cantidad mayor quedan ⌊r/2j⌋\lfloor r/2^j \rfloor símbolos, que es 0 en cuanto 2j>r2^j > r, es decir, cuando j=⌊log⁡2r⌋+1j = \lfloor \log_2 r \rfloor + 1. Después de esas hay a lo sumo una pasada más, la que no encuentra nada. Son a lo sumo ⌊log⁡2n⌋+2\lfloor \log_2 n \rfloor + 2 pasadas, y

(2n+1)(⌊log⁡2n⌋+2)=O(nlog⁡n).(2n + 1)(\lfloor \log_2 n \rfloor + 2) = O(n \log n).

∎

Con la entrada 0k1k\mathtt{0}^k\mathtt{1}^k la cuenta se puede hacer exacta, y da 2n⌊log⁡2n⌋+n+12n\lfloor \log_2 n \rfloor + n + 1 pasos para n=2k≥2n = 2k \geq 2. Para n=10n = 10 son 2⋅10⋅3+11=712 \cdot 10 \cdot 3 + 11 = 71, lo que imprimió run_tm. Las pruebas comprueban esa fórmula, y que la cota de la demostración vale para todas las cadenas de longitud a lo sumo 12.

Entonces A∈TIME(nlog⁡n)A \in \mathsf{TIME}(n \log n). ¿Se puede bajar más con una cinta? No. Se demuestra que todo lenguaje que una máquina de una cinta decide en tiempo estrictamente menor que nlog⁡nn \log n (en el sentido de la oo minúscula) es regular, y AA no lo es. No lo demostraremos, pero conviene saberlo: con una cinta, nlog⁡nn \log n es lo mejor posible para este lenguaje.

Con dos cintas: O(n)

Con una segunda cinta el problema se vuelve trivial. La máquina copia los ceros a la cinta 2 y después, por cada 1\mathtt{1} que lee en la cinta 1, retrocede un 0\mathtt{0} en la cinta 2. Los dos cabezales se mueven a la vez, y nadie tiene que cruzar la entrada de ida y vuelta.

M3 = "Con la entrada w en la cinta 1:
  1. Si la entrada es vacía, aceptar. Si empieza con 1, rechazar.
  2. Escribir $ en la primera celda de la cinta 2.
  3. Avanzar en la cinta 1 mientras haya ceros, copiando cada uno a la cinta 2.
  4. Avanzar en la cinta 1 mientras haya unos, retrocediendo una celda en la cinta 2 por
     cada uno. Si aparece un 0, rechazar.
  5. Si la cinta 1 llega al blanco justo cuando la cinta 2 vuelve al $, aceptar.
     Si no, rechazar."

La cinta 2 funciona como la pila del autómata de la semana 6: guarda una marca de fondo y un símbolo por cada cero. code/formats.md no define un formato para máquinas de varias cintas, así que esta máquina no tiene archivo: está escrita en C++ en multitape.h, con una función de transición que recibe un símbolo por cinta, y tres estados además de los finales.

Cada paso avanza el cabezal de la cinta 1, salvo dos: el que escribe la marca $ y el que pasa de copiar a comparar. Con el paso final que acepta, son a lo sumo n+3n + 3 pasos. El tiempo de M3M_3 es O(n)O(n).

Contar los pasos de verdad

El programa count_steps ejecuta las tres máquinas. Su primera tabla aplica la definición de tiempo al pie de la letra: para cada longitud nn hasta 12, prueba las 2n2^n entradas y se queda con el máximo.

$ build/count_steps
Peor caso sobre las 2^n entradas de longitud n: pasos, y la primera entrada que los alcanza
 n   cuadrática            n log n               dos cintas
 0    1  ε                  1  ε                  1  ε              
 1    2  0                  2  0                  3  0              
 2    5  01                 7  00                 5  01             
 3    8  001                4  000                6  001            
 4   13  0011              21  0000               7  0001           
 5   18  00011              6  00000              8  00001          
 6   25  000111            31  000001             9  000001         
 7   32  0000111            8  0000000           10  0000001        
 8   41  00001111          57  00000000          11  00000001       
 9   50  000001111         10  000000000         12  000000001      
10   61  0000011111        71  0000000001        13  0000000001     
11   72  00000011111       12  00000000000       14  00000000001    
12   85  000000111111      85  000000000011      15  000000000001   

Vale la pena detenerse en tres cosas.

El peor caso no siempre es una cadena del lenguaje. Para la máquina cuadrática con n=5n = 5, la entrada más lenta es 00011\mathtt{00011}, que se rechaza: la máquina hace dos rondas completas y recién en la tercera descubre que falta un uno. En estas longitudes, su tiempo exacto es ⌈(n+1)2/2⌉\lceil (n + 1)^2 / 2 \rceil.

El tiempo no tiene por qué crecer con nn. La máquina de nlog⁡nn \log n tarda 57 pasos en el peor caso con n=8n = 8 y solo 10 con n=9n = 9. Con longitud impar, las cantidades de ceros y de unos tienen distinta paridad, y la máquina rechaza al terminar la primera pasada, en a lo sumo n+1n + 1 pasos. La definición de tiempo no pide que ff sea creciente, y la notación OO absorbe estas irregularidades: lo que se afirma es una cota superior.

Varias entradas pueden empatar. Para n=4n = 4, la máquina de nlog⁡nn \log n tarda lo mismo con 0000\mathtt{0000} que con 0011\mathtt{0011}: 4 y 0 tienen la misma paridad, y 2 y 0 también, así que hacen falta tres pasadas para rechazar. La tabla muestra la primera entrada, en orden, que alcanza el máximo.

La segunda tabla usa solo las entradas 0k1k\mathtt{0}^k\mathtt{1}^k, para llegar a longitudes grandes:

Pasos con la entrada 0^k 1^k, de longitud n = 2k
    n   cuadrática   pasos/n²    n log n   pasos/(n·log₂ n)   dos cintas
   16          145      0.566        145              2.266           19
   32          545      0.532        353              2.206           35
   64         2113      0.516        833              2.169           67
  128         8321      0.508       1921              2.144          131
  256        33025      0.504       4353              2.125          259
  512       131585      0.502       9729              2.111          515
 1024       525313      0.501      21505              2.100         1027
 2048      2099201      0.500      47105              2.091         2051
 4096      8392705      0.500     102401              2.083         4099
 8192     33562625      0.500     221185              2.077         8195

Con n=16n = 16 las dos máquinas de una cinta empatan en 145 pasos. Con n=8192n = 8192, la cuadrática da más de 33 millones de pasos y la otra 221 185: unas 150 veces menos. Cada vez que nn se duplica, la primera columna se multiplica por casi 4 y la tercera por algo más de 2. Las columnas de cocientes confirman las dos fórmulas: la primera tiende a 1/21/2, y la segunda baja despacio hacia 2. La máquina de dos cintas da siempre n+3n + 3 pasos.

Gráfico de los pasos de las tres máquinas con la entrada 0^k 1^k, contra la longitud n de la entrada, de 2 a 64. La curva de M1, de una cinta, es una parábola, n²/2 + n + 1: pasa por 545 pasos en n = 32 y llega a 2113 en n = 64. La de M2, de una cinta, 2n⌊log₂ n⌋ + n + 1, crece casi en línea recta con un salto en cada potencia de 2: 353 pasos en n = 32 y 833 en n = 64. La de M3, de dos cintas, n + 3, queda pegada al eje: 35 y 67 pasos. Una marca señala que en n = 16 las dos máquinas de una cinta empatan en 145 pasos.Gráfico de los pasos de las tres máquinas con la entrada 0^k 1^k, contra la longitud n de la entrada, de 2 a 64. La curva de M1, de una cinta, es una parábola, n²/2 + n + 1: pasa por 545 pasos en n = 32 y llega a 2113 en n = 64. La de M2, de una cinta, 2n⌊log₂ n⌋ + n + 1, crece casi en línea recta con un salto en cada potencia de 2: 353 pasos en n = 32 y 833 en n = 64. La de M3, de dos cintas, n + 3, queda pegada al eje: 35 y 67 pasos. Una marca señala que en n = 16 las dos máquinas de una cinta empatan en 145 pasos.
Las tres máquinas deciden el mismo lenguaje. Hasta n = 16 las dos de una cinta van parejas; desde ahí la cuadrática se despega, y la de dos cintas casi no se mueve.

Son conteos de pasos y no tiempos de reloj: salen iguales en cualquier computadora.

Idea clave. Para un mismo lenguaje, el costo depende del modelo: O(nlog⁡n)O(n \log n) es lo mejor con una cinta, y con dos se llega a O(n)O(n). En computabilidad esto no pasaba: todos los modelos razonables decidían los mismos lenguajes. En complejidad, el modelo cambia el exponente.

El modelo importa, pero solo polinomialmente

Si la clase TIME(n)\mathsf{TIME}(n) depende de cuántas cintas tiene la máquina, ¿sirve de algo una teoría construida sobre un modelo tan arbitrario? Sirve, porque la diferencia entre modelos está acotada. En la semana 7 vieron que una máquina de una cinta simula a una de varias, y contaron sus pasos. Ahora lo decimos en función de t(n)t(n).

Teorema. Sea t(n)t(n) una función con t(n)≥nt(n) \geq n. Toda máquina de Turing de varias cintas que corre en tiempo t(n)t(n) tiene una máquina equivalente de una cinta que corre en tiempo O(t(n)2)O(t(n)^2).

La condición t(n)≥nt(n) \geq n solo descarta máquinas que no alcanzan a leer su entrada.

Demostración. Por construcción: es la simulación de la semana 7, con el mismo conteo de pasos, que repasamos.

Qué se construye. Sea MM una máquina de kk cintas que corre en tiempo t(n)t(n). La máquina SS, de una cinta, guarda en su cinta el contenido de las kk cintas de MM, una después de otra, separadas por el símbolo #\mathtt{\#}. En cada tramo, un símbolo lleva una marca: es la posición del cabezal de MM en esa cinta.

cintas de M:    0 1 [1] 0 _ ...        a [b] _ ...        [_] ...
cinta de S:     # 0 1 1' 0 # a b' # _' #          (la comilla es la marca del cabezal)

SS trabaja así:

S = "Con la entrada w:
  1. Dar a la cinta el formato inicial: # w con su primer símbolo marcado, y después
     k − 1 tramos con un solo blanco marcado, cada uno cerrado por #.
  2. Para simular un paso de M: recorrer la cinta desde el primer # hasta el último,
     recordando en el estado los k símbolos marcados.
  3. Volver al inicio y recorrer otra vez, aplicando la transición de M en cada tramo:
     escribir el símbolo nuevo y mover la marca una celda.
  4. Si una marca debe pasar a la derecha del último símbolo de su tramo, cae sobre un #.
     En ese caso, escribir ahí un blanco marcado y desplazar una celda a la derecha
     todo lo que sigue, hasta el último #.
  5. Si M entra a su estado de aceptación, aceptar; si entra al de rechazo, rechazar.
     Si no, repetir desde el paso 2."

Por qué es equivalente. Es lo que se demostró en la semana 7: después de simular cada paso, la cinta de SS describe exactamente las cintas y los cabezales de MM. SS acepta, rechaza o sigue según lo haga MM.

Cuánto cuesta. Todo depende de qué tan larga es la parte usada de la cinta de SS.

  • En t(n)t(n) pasos, cada cabezal de MM se aleja a lo sumo t(n)t(n) celdas del inicio de su cinta. La cinta 1 tiene además la entrada, de longitud n≤t(n)n \leq t(n). Así que cada tramo tiene a lo sumo t(n)+1t(n) + 1 celdas, y la parte usada de la cinta de SS tiene a lo sumo k(t(n)+1)+k+1k(t(n) + 1) + k + 1 celdas. Como kk es una constante de MM, eso es O(t(n))O(t(n)).
  • El paso 1 cuesta O(n+k)O(n + k): hay que correr la entrada una celda para poner el primer #\mathtt{\#}, llevando cada símbolo en el estado, y escribir los otros tramos. Como n≤t(n)n \leq t(n), es O(t(n))O(t(n)).
  • Simular un paso de MM cuesta dos recorridos de la parte usada, O(t(n))O(t(n)) cada uno, más a lo sumo kk desplazamientos, uno por cinta, y cada desplazamiento recorre a lo sumo la parte usada: O(t(n))O(t(n)) cada uno. En total, un paso de MM cuesta O(t(n))O(t(n)) pasos de SS.
  • MM da a lo sumo t(n)t(n) pasos.

Sumando:

O(t(n))+t(n)⋅O(t(n))=O(t(n)2).O(t(n)) + t(n) \cdot O(t(n)) = O(t(n)^2).

∎

El cuadrado sale de multiplicar dos cosas que crecen con t(n)t(n): la cantidad de pasos simulados, y la longitud de cinta que SS recorre para simular cada uno. La máquina de varias cintas tiene sus cabezales donde los necesita, y la de una cinta tiene que ir a buscarlos.

El teorema da una cota superior y no dice que la simulación sea la mejor manera de pasar a una cinta. Para nuestro lenguaje AA, la máquina de dos cintas corre en O(n)O(n) y el teorema promete una de una cinta en O(n2)O(n^2); ya vimos que existe una mejor, en O(nlog⁡n)O(n \log n).

La clase P

Entre t(n)t(n) y t(n)2t(n)^2 hay una diferencia enorme si uno compara algoritmos. Pero hay una propiedad que el cuadrado no rompe: si t(n)t(n) es un polinomio, t(n)2t(n)^2 también lo es.

Definición. P\mathsf{P} es la clase de los lenguajes que una máquina de Turing determinista de una cinta decide en tiempo polinomial:

P=⋃k≥1TIME(nk)=TIME(n)∪TIME(n2)∪TIME(n3)∪⋯\mathsf{P} = \bigcup_{k \geq 1} \mathsf{TIME}(n^k) = \mathsf{TIME}(n) \cup \mathsf{TIME}(n^2) \cup \mathsf{TIME}(n^3) \cup \cdots

Un lenguaje está en P si para algún kk fijo hay una máquina que lo decide en tiempo O(nk)O(n^k). El exponente puede ser cualquiera, pero no depende de la entrada.

Corolario. P es la misma clase si se define con máquinas de varias cintas.

Demostración. Si una máquina de una cinta decide LL en tiempo O(nk)O(n^k), ella misma es una máquina de varias cintas que no usa las demás. En la otra dirección, si una máquina de jj cintas decide LL en tiempo O(nk)O(n^k), con k≥1k \geq 1, el teorema anterior da una de una cinta en tiempo O((nk)2)=O(n2k)O((n^k)^2) = O(n^{2k}), que sigue siendo polinomial. ∎

Esto es lo que responde la primera pregunta de repaso de la guía: la cota que se usa es O(t(n)2)O(t(n)^2), y lo que importa de ella es que el cuadrado de un polinomio es un polinomio.

Lo mismo pasa con los demás modelos deterministas que conocen. Una máquina con la cinta infinita en los dos sentidos, una con una cinta de dos dimensiones, una computadora con memoria de acceso directo, un programa en C++: cada uno se puede simular en una máquina de Turing de una cinta de modo que t(n)t(n) pasos del modelo cuesten a lo sumo t(n)ct(n)^c pasos de la máquina, para alguna constante cc que depende del modelo y no de la entrada. Se dice que esos modelos son polinomialmente equivalentes. No es un teorema, porque “modelo razonable” no tiene una definición: es una observación que se ha comprobado con cada modelo determinista propuesto hasta hoy, del mismo modo que la tesis de Church-Turing.

Hay una condición escondida en la palabra “razonable”: el modelo no puede hacer en un paso una cantidad de trabajo que crezca sin control. Una computadora idealizada que multiplica en un solo paso dos números de cualquier tamaño no es razonable: elevando al cuadrado nn veces fabrica un número de 2n2^n bits en nn pasos. En los modelos razonables, una operación sobre números cuesta según la cantidad de bits que tienen.

Idea clave. P no depende del modelo determinista que se use para definirla. Por eso desde ahora se puede volver a escribir en alto nivel: para mostrar que un lenguaje está en P no hace falta dar la tabla de una máquina de una cinta. Basta un algoritmo y una cuenta de que es polinomial.

Cómo se demuestra que un lenguaje está en P

Desde aquí, las máquinas se describen otra vez en alto nivel, como desde la semana 9, y se agrega el análisis del tiempo. Para mostrar que un algoritmo corre en tiempo polinomial hay que comprobar tres cosas.

  1. La cantidad de etapas es polinomial en la longitud nn de la entrada, contando las repeticiones de los ciclos.
  2. Cada etapa se puede hacer en tiempo polinomial en un modelo determinista razonable. Recorrer la entrada, comparar dos números, buscar un arco en una lista: todo eso es polinomial.
  3. La entrada está codificada de una manera razonable, que es el tema de la sección siguiente.

Funciona porque los polinomios son cerrados bajo las operaciones que aparecen: la suma, el producto y la composición de dos polinomios son polinomios. Una cantidad polinomial de etapas, cada una de costo polinomial, da un costo polinomial.

¿Por qué “polinomial” como sinónimo de “tratable”? No porque n100n^{100} sea rápido. Las razones son tres. Primera, la que acabamos de ver: es la clase más pequeña que contiene al tiempo lineal y no cambia al cambiar de modelo. Segunda, es cerrada por composición: un algoritmo polinomial que llama a subrutinas polinomiales sigue siendo polinomial, y eso es lo que hará funcionar a las reducciones de la semana 13. Tercera, una observación empírica: los problemas naturales que están en P casi siempre terminan con algoritmos de exponente pequeño, y la diferencia entre polinomial y exponencial es la que en la práctica separa lo que se puede calcular de lo que no. Con n=100n = 100, n3n^3 es un millón y 2n2^n tiene 31 dígitos.

La codificación de la entrada

El tiempo se mide contra la longitud de la cadena de entrada. Entonces importa cómo se escriben los objetos como cadenas. En la semana 7 se introdujo la notación ⟨G⟩\langle G \rangle para la codificación de un grafo y ⟨M⟩\langle M \rangle para la de una máquina, y se dijo que cualquier codificación servía. Para la computabilidad es verdad. Para el tiempo hay que pedir un poco más: que la codificación sea razonable, es decir, que no infle la entrada.

Para casi todos los objetos, todas las codificaciones naturales dan longitudes parecidas, y la elección no cambia nada.

  • Un grafo de mm vértices se puede escribir como matriz de adyacencia, con m2m^2 bits, o como lista de arcos, con a lo sumo m2m^2 pares de números de ⌈log⁡2m⌉\lceil \log_2 m \rceil bits. Cada longitud está acotada por un polinomio en la otra, y las dos están entre mm y un polinomio en mm. Por eso, para grafos, “polinomial en la longitud de ⟨G⟩\langle G \rangle” y “polinomial en la cantidad de vértices” son lo mismo, y se puede seguir contando en vértices y arcos como en Algoritmos. Vértice y nodo son lo mismo, y un arco es una arista con dirección; las semanas 13 y 14 dicen nodo y arista también para los grafos dirigidos.
  • Una fórmula, una gramática, un autómata: lo mismo. Su longitud es, salvo un factor logarítmico por los nombres, la cantidad de símbolos que uno escribe en el papel.

Hay un objeto con el que sí hay que tener cuidado: los números.

Binario y unario

Un número xx se puede escribir en binario, con ⌊log⁡2x⌋+1\lfloor \log_2 x \rfloor + 1 bits, o en unario, con xx palotes: el 5 como 11111\mathtt{11111}. La primera tabla de encoding_demo compara:

$ build/encoding_demo
Un número x, en binario y en unario
        x   en binario             bits   símbolos en unario
        5   101                       3                    5
       12   1100                      4                   12
      100   1100100                   7                  100
     1000   1111101000               10                 1000
  1000000   11110100001001000000     20              1000000

La escritura en unario es exponencialmente más larga que la binaria: un número de bb bits vale hasta 2b−12^b - 1. Entre binario, decimal y cualquier otra base mayor que 1 no hay ese problema, porque las longitudes difieren en un factor constante: log⁡10x=log⁡2x/log⁡210\log_{10} x = \log_2 x / \log_2 10.

La convención de este curso, y de toda la teoría de la complejidad, es:

Los números se escriben en binario. La longitud de un número xx en la entrada es ⌊log⁡2x⌋+1\lfloor \log_2 x \rfloor + 1, aproximadamente log⁡2x\log_2 x.

La consecuencia sorprende la primera vez. Un algoritmo que recibe el número xx y da ”xx pasos” no es de tiempo lineal: es de tiempo exponencial. Su entrada mide n=log⁡2xn = \log_2 x símbolos, y da x=2nx = 2^n pasos.

El ejemplo clásico es decidir si un número es primo probando divisores. El lenguaje es

PRIMES={ x:x es un nuˊmero primo, escrito en binario },\mathrm{PRIMES} = \{\, x : x \text{ es un número primo, escrito en binario} \,\},

y el algoritmo prueba d=2,3,4,…d = 2, 3, 4, \ldots mientras d2≤xd^2 \leq x. Si xx es primo, hace ⌊x⌋−1\lfloor \sqrt{x} \rfloor - 1 divisiones. La segunda tabla del programa lo ejecuta con el mayor primo de bb bits, para varios bb:

¿Es primo x? Divisiones de prueba hasta la raíz, con el mayor primo de b bits
 b                  x    divisiones
 8                251            14
16              65521           254
24           16777213          4094
32         4294967291         65534
40      1099511627689       1048574

La entrada crece de 8 en 8 bits, y las divisiones se multiplican por 16 cada vez. Un número de bb bits es cercano a 2b2^b, su raíz a 2b/22^{b/2}, y 28/2=162^{8/2} = 16. La cantidad de divisiones es x≈2n/2\sqrt{x} \approx 2^{n/2}, con nn la longitud de la entrada: exponencial. Con un número de 2048 bits, como los que se usan en criptografía, serían unas 210242^{1024} divisiones.

Es la segunda pregunta de repaso de la guía. ¿Es polinomial probar divisores hasta x\sqrt{x}? Es polinomial en el valor de xx, y hasta mejor: es x\sqrt{x}. Pero no es polinomial en la longitud de la entrada, que es lo que cuenta. (Que este algoritmo sea exponencial no dice que el problema sea difícil: en 2002, Agrawal, Kayal y Saxena demostraron que PRIMES\mathrm{PRIMES} está en P, con un algoritmo completamente distinto.)

Error común. Medir el tiempo en función del valor de un número de la entrada, y no de la longitud de su representación. “El ciclo da xx vueltas, así que es lineal” es falso si xx es un número de la entrada: la entrada tiene log⁡2x\log_2 x símbolos, y xx vueltas son exponenciales en eso. Antes de decir “polinomial”, pregunten: ¿polinomial en qué?

Pseudopolinomial: la mochila otra vez

En Algoritmos resolvieron la mochila 0/1 con programación dinámica, en tiempo O(nW)O(nW), donde nn es la cantidad de objetos y WW la capacidad. Allá se dijo que ese costo “parece polinomial y no lo es”, y se le dio un nombre: pseudopolinomial. Con la definición de esta semana se ve exactamente por qué.

Tomemos un pariente más simple de la mochila, que usaremos toda la semana. En suma de subconjuntos hay una lista de números positivos x1,…,xnx_1, \ldots, x_n y un objetivo tt, y se pregunta si algunos de los números suman exactamente tt:

SUBSET-SUM={ ⟨x1,…,xn,t⟩:alguˊn subconjunto de los xi suma t }\mathrm{SUBSET\text{-}SUM} = \{\, \langle x_1, \ldots, x_n, t \rangle : \text{algún subconjunto de los } x_i \text{ suma } t \,\}

La programación dinámica es la misma de la mochila: una tabla que dice, para cada suma cc de 0 a tt, si se puede alcanzar con los números vistos hasta ahora. Son n⋅(t+1)n \cdot (t + 1) casillas. La tercera tabla de encoding_demo toma 10 números de bb bits y como objetivo la mitad de su suma, y cuenta las casillas:

SUBSET-SUM con la tabla de Algoritmos: 10 números de b bits, objetivo la mitad de la suma
 b   bits de la entrada   casillas de la tabla
 4                   46                    550
 8                   90                   8730
12                  134                 139530
16                  178                2232330

La cantidad de números no cambia: siempre son 10. Solo cambia cuántos bits tiene cada uno. La entrada crece de 46 a 178 bits, menos de 4 veces, y la tabla crece 4000 veces: se multiplica por 16 cada vez que los números ganan 4 bits. Con números de 64 bits, la entrada tendría unos 700 bits y la tabla más de 102010^{20} casillas.

La cuenta general: si los nn números tienen bb bits, la entrada mide unos (n+1)⋅b(n + 1) \cdot b bits, y tt puede valer hasta n⋅2bn \cdot 2^b. La tabla tiene unas n2⋅2bn^2 \cdot 2^b casillas: polinomial en nn, exponencial en bb.

Definición. Un algoritmo es de tiempo pseudopolinomial si su tiempo es polinomial en la longitud de la entrada y en el valor de los números que contiene. Dicho de otro modo: sería polinomial si los números se escribieran en unario.

El algoritmo de la tabla es pseudopolinomial. Si los números vinieran en unario, la entrada mediría más de tt símbolos, porque el propio tt ocuparía tt palotes, y más de nn, y las n(t+1)n(t + 1) casillas serían menos que el cuadrado de su longitud. Es decir: suma de subconjuntos con los números en unario está en P, y con los números en binario no se sabe. La codificación cambió la clase del problema.

Figura en tres partes. Arriba, el número 12 escrito de dos maneras: en binario, 1100, con n = 4 símbolos, y en unario, doce palotes, con n = 12 símbolos. Al centro, un algoritmo que recibe el número x y da x pasos: con x en binario, n es aproximadamente log₂ x y los x pasos son unos 2^n, exponencial en n; con x en unario, n = x y son n pasos, lineal en n. Abajo, la tabla de SUBSET-SUM de encoding_demo con 10 números de b bits: para b = 4, 8, 12 y 16 la entrada mide 46, 90, 134 y 178 bits, y la tabla tiene 550, 8730, 139 530 y 2 232 330 casillas. La entrada crece menos de 4 veces y la tabla, 4000 veces.Figura en tres partes. Arriba, el número 12 escrito de dos maneras: en binario, 1100, con n = 4 símbolos, y en unario, doce palotes, con n = 12 símbolos. Al centro, un algoritmo que recibe el número x y da x pasos: con x en binario, n es aproximadamente log₂ x y los x pasos son unos 2^n, exponencial en n; con x en unario, n = x y son n pasos, lineal en n. Abajo, la tabla de SUBSET-SUM de encoding_demo con 10 números de b bits: para b = 4, 8, 12 y 16 la entrada mide 46, 90, 134 y 178 bits, y la tabla tiene 550, 8730, 139 530 y 2 232 330 casillas. La entrada crece menos de 4 veces y la tabla, 4000 veces.
«Polinomial» siempre es polinomial en la longitud de la entrada. El mismo algoritmo es lineal si el número viene en unario y exponencial si viene en binario: eso es ser pseudopolinomial.

Esto responde una pregunta que quedó de Algoritmos: si la mochila se resuelve en O(nW)O(nW) y la mochila es NP-completa, ¿por qué eso no demuestra que P=NP\mathsf{P} = \mathsf{NP}? Porque O(nW)O(nW) no es tiempo polinomial en la longitud de la entrada.

En la práctica. Pseudopolinomial no quiere decir inútil. Si los números de la entrada son pequeños (capacidades de unos miles, montos en céntimos), la tabla es la mejor herramienta. El adjetivo avisa de qué depende: de la magnitud de los números, y no de cuántos son.

Dos problemas en P: PATH y los lenguajes libres de contexto

Dos ejemplos con el patrón completo: un intento que no es polinomial, el algoritmo que sí lo es, y la cuenta.

PATH

PATH={ ⟨G,s,t⟩:G es un grafo dirigido que tiene un camino de s a t }\mathrm{PATH} = \{\, \langle G, s, t \rangle : G \text{ es un grafo dirigido que tiene un camino de } s \text{ a } t \,\}

El intento que no sirve. Probar todos los caminos posibles. Si GG tiene mm vértices, un camino sin vértices repetidos es una secuencia de a lo sumo mm vértices, y hay del orden de mmm^m secuencias. Revisarlas todas es exponencial.

El algoritmo. El de Algoritmos: marcar lo alcanzable. No hace falta la cola de la búsqueda en anchura, porque aquí no importa ser lineal, solo polinomial.

M = "Con la entrada ⟨G, s, t⟩, donde G es un grafo dirigido con los vértices s y t:
  1. Marcar el vértice s.
  2. Repetir hasta que no se marque ningún vértice nuevo:
  3.     Recorrer todos los arcos de G. Si un arco (a, b) va de un vértice marcado
         a uno sin marcar, marcar b.
  4. Si t está marcado, aceptar. Si no, rechazar."

Es correcto. Un vértice queda marcado si y solo si hay un camino de ss a él. Todo vértice marcado es alcanzable, por inducción sobre el momento en que se marca: ss lo es, y bb se marca por un arco desde un vértice aa que ya era alcanzable. Y todo vértice alcanzable queda marcado, por inducción sobre la longitud del camino: si el último arco del camino es (a,b)(a, b) y aa quedó marcado, el ciclo no puede terminar con bb sin marcar.

Es polinomial. Las etapas 1 y 4 se ejecutan una vez. La etapa 3 se repite a lo sumo mm veces: cada repetición, salvo la última, marca al menos un vértice nuevo, y hay mm vértices. Cada repetición recorre todos los arcos, que son a lo sumo m2m^2, y para cada uno consulta y cambia marcas, que en una máquina de Turing es recorrer la cinta: polinomial. Una cantidad polinomial de etapas, cada una polinomial. Entonces PATH∈P\mathrm{PATH} \in \mathsf{P}.

La máquina de Turing que hace esto es mucho más lenta que la búsqueda en anchura de Algoritmos, que es O(m+arcos)O(m + \text{arcos}) en una computadora real. No importa: para estar en P solo hace falta algún polinomio.

Todo lenguaje libre de contexto está en P

Teorema. Todo lenguaje libre de contexto está en P.

Demostración. Por construcción de un decididor: el algoritmo CYK de la semana 5. Sea LL un lenguaje libre de contexto. Tiene una gramática GG en forma normal de Chomsky, donde cada regla es A→BCA \to BC o A→aA \to a, más S→εS \to \varepsilon si la cadena vacía está en LL.

El intento que no sirve. En la semana 9 se usó el teorema de la semana 5: en forma normal de Chomsky, una derivación de una cadena de longitud n≥1n \geq 1 tiene exactamente 2n−12n - 1 pasos, y eso bastó para decidir ACFGA_{\mathrm{CFG}}: se prueban todas las derivaciones de esa longitud. Para decidir alcanza, pero cada paso puede elegir entre varias reglas, y la cantidad de derivaciones crece exponencialmente con nn.

El algoritmo. Programación dinámica sobre las subcadenas. T[i][j]T[i][j] es el conjunto de las variables que generan la subcadena de ww que va de la posición ii a la jj.

algoritmo cyk(w, G)
    n ← |w|
    si n = 0 entonces
        devolver (S → ε es una regla de G)
    fin si
    para i desde 0 hasta n − 1
        T[i][i] ← { A : A → w[i] es una regla de G }
    fin para
    para l desde 2 hasta n                      // l es la longitud de la subcadena
        para i desde 0 hasta n − l
            j ← i + l − 1
            T[i][j] ← ∅
            para k desde i hasta j − 1          // la subcadena se parte después de la posición k
                para cada regla A → BC de G
                    si B ∈ T[i][k] y C ∈ T[k + 1][j] entonces
                        agregar A a T[i][j]
                    fin si
                fin para
            fin para
        fin para
    fin para
    devolver (S ∈ T[0][n − 1])
fin algoritmo

Es correcto. Es lo que se demostró en la semana 5: una variable AA genera una subcadena de longitud al menos 2 si y solo si alguna regla A→BCA \to BC la parte en dos trozos, con BB generando el primero y CC el segundo.

Es polinomial. Hay tres ciclos anidados sobre posiciones, cada uno de a lo sumo nn vueltas, y uno sobre las reglas. El punto fino es este último: la gramática no es parte de la entrada. LL es un lenguaje fijo, GG es una gramática fija para él, y la cantidad de reglas es una constante. La entrada es solo ww. El algoritmo hace O(n3)O(n^3) operaciones sobre la tabla, cada una polinomial en una máquina de Turing. Entonces L∈PL \in \mathsf{P}. ∎

Con esto, las clases de las dos primeras partes del curso quedan ubicadas dentro de la cuarta: todo lenguaje regular se decide en tiempo lineal, con un DFA, y todo lenguaje libre de contexto, en tiempo polinomial.

regulares⊊libres de contexto⊊P\text{regulares} \subsetneq \text{libres de contexto} \subsetneq \mathsf{P}

La segunda inclusión es estricta porque { anbncn:n≥0 }\{\, \mathtt{a}^n\mathtt{b}^n\mathtt{c}^n : n \geq 0 \,\} no es libre de contexto, y una máquina lo decide en tiempo polinomial con la misma idea de M1M_1.

El no determinismo parece costar caro

Queda la otra variante de la semana 7: la máquina no determinista. Primero hay que decir qué es su tiempo.

Definición. Sea NN una máquina de Turing no determinista que es un decididor: con toda entrada, todas las ramas de su ejecución se detienen. El tiempo de NN es la función f(n)f(n) que da el máximo número de pasos de cualquier rama, con cualquier entrada de longitud nn.

Es la profundidad máxima del árbol de ejecuciones. No cuenta cuántas ramas hay: una máquina no determinista de tiempo nn puede tener 2n2^n ramas, cada una de nn pasos.

Recuerden cuándo acepta: NN acepta ww si alguna rama termina en qacceptq_{\text{accept}}, y la rechaza si todas terminan en qrejectq_{\text{reject}}.

Teorema. Sea t(n)t(n) una función con t(n)≥nt(n) \geq n. Toda máquina de Turing no determinista de una cinta que corre en tiempo t(n)t(n) tiene una máquina determinista de una cinta equivalente que corre en tiempo 2O(t(n))2^{O(t(n))}.

Demostración. Por construcción: una variante de la simulación de la semana 7, que recorre el árbol de ejecuciones por niveles. Allí la máquina guardaba una cola de configuraciones. Aquí guarda solo la lista de decisiones que lleva a cada nodo, que es más fácil de contar.

Sea NN la máquina no determinista y bb la mayor cantidad de opciones que su función de transición ofrece en algún par de estado y símbolo. Con una entrada de longitud nn:

  • El árbol de ejecuciones tiene profundidad a lo sumo t(n)t(n), y cada nodo tiene a lo sumo bb hijos. Tiene a lo sumo bt(n)b^{t(n)} hojas, y en total a lo sumo 1+b+b2+⋯+bt(n)≤2 bt(n)1 + b + b^2 + \cdots + b^{t(n)} \leq 2\,b^{t(n)} nodos, cuando b≥2b \geq 2.
  • La simulación visita los nodos por niveles, y para llegar a un nodo vuelve a ejecutar NN desde la raíz siguiendo la lista de decisiones que lleva a él: O(t(n))O(t(n)) pasos por nodo.

El total es O(t(n)⋅bt(n))O(t(n) \cdot b^{t(n)}). Para ponerlo en la forma del enunciado:

t(n)⋅bt(n)=2log⁡2t(n)⋅2t(n)log⁡2b=2O(t(n)),t(n) \cdot b^{t(n)} = 2^{\log_2 t(n)} \cdot 2^{t(n) \log_2 b} = 2^{O(t(n))},

porque log⁡2b\log_2 b es una constante y log⁡2t(n)≤t(n)\log_2 t(n) \leq t(n). Esa simulación se describe con varias cintas: una para la entrada, una para la cinta de NN y una para la lista de decisiones. Por el teorema anterior, pasar a una cinta eleva el tiempo al cuadrado, y (2O(t(n)))2=2O(t(n))\left(2^{O(t(n))}\right)^2 = 2^{O(t(n))}: el cuadrado solo duplica la constante del exponente. ∎

Comparen los dos teoremas de simulación.

De A una cinta determinista Un polinomio se vuelve
Varias cintas, tiempo t(n)t(n) O(t(n)2)O(t(n)^2) Otro polinomio
No determinista, tiempo t(n)t(n) 2O(t(n))2^{O(t(n))} Una exponencial

El primero dice que agregar cintas no saca de P. El segundo no dice lo mismo del no determinismo: la única simulación que conocemos convierte tiempo polinomial en tiempo exponencial. Es solo una cota superior. Nadie ha demostrado que haga falta tanto, y nadie ha encontrado una simulación mejor. La distancia entre esas dos cosas es la pregunta P\mathsf{P} contra NP\mathsf{NP}, y es el tema de la sesión B.

Idea clave. Las máquinas de varias cintas y las de una cinta son polinomialmente equivalentes. Las deterministas y las no deterministas, no se sabe. Por eso la definición de P dice “determinista”, y la clase que se obtiene quitando esa palabra recibe otro nombre.

Encontrar frente a comprobar

Un camino hamiltoniano en un grafo dirigido es un camino que pasa por cada vértice 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 \,\}

Se parece a PATH\mathrm{PATH}, y cambia una sola palabra: el camino tiene que pasar por todos los vértices. Con ese cambio, la idea de marcar lo alcanzable ya no sirve, y nadie conoce un algoritmo de tiempo polinomial. Todos los que se conocen tardan tiempo exponencial. El más directo prueba los ordenamientos de los vértices, y un grafo de mm vértices tiene m!m! ordenamientos.

Pero HAMPATH\mathrm{HAMPATH} tiene una propiedad que lo distingue de un problema arbitrario. Si alguien les entrega un camino hamiltoniano, comprobar que lo es resulta fácil: se revisa que estén todos los vértices, que no se repita ninguno, que empiece en ss, que termine en tt y que cada paso siga un arco del grafo. Eso es tiempo polinomial, sin duda.

El programa verify_demo lo hace con un grafo de 5 vértices:

$ build/verify_demo
HAMPATH: grafo dirigido con 5 vértices y los arcos
  1→2 2→3 3→4 4→5 1→3 3→2 2→4 5→1
  s = 1, t = 5
  c = 1 2 3 4 5     válido
  c = 1 3 2 4 5     válido
  c = 1 3 4 5       inválido   tiene 4 vértices y no 5
  c = 1 2 2 4 5     inválido   repite el vértice 2
  c = 1 2 3 4 6     inválido   el vértice 6 no existe
  c = 1 2 4 3 5     inválido   no hay arco 4→3
  c = 2 3 4 5 1     inválido   es un camino hamiltoniano, pero no de s a t

Hay 120 ordenamientos de 5 vértices, y solo esos dos son caminos hamiltonianos de 1 a 5. Quien busca tiene que dar con uno de los dos. Quien comprueba solo mira la lista que recibió.

Esa asimetría entre encontrar una solución y comprobar una que ya está escrita es la idea de la clase NP. La conocen de la vida diaria: resolver un sudoku lleva un rato, y revisar uno resuelto, un minuto. En Algoritmos la usaron con el nombre de certificado. Ahora va la definición precisa.

Verificadores y la clase NP

Definición. Un verificador (verifier) de un lenguaje AA es un algoritmo VV tal que

A={ w:V acepta ⟨w,c⟩ para alguna cadena c }.A = \{\, w : V \text{ acepta } \langle w, c \rangle \text{ para alguna cadena } c \,\}.

La cadena cc es un certificado (certificate) de que w∈Aw \in A. El tiempo de un verificador se mide solo en función de la longitud de ww. Un verificador de tiempo polinomial corre en tiempo polinomial en ∣w∣|w|.

Definición. NP\mathsf{NP} es la clase de los lenguajes que tienen un verificador de tiempo polinomial.

La definición es corta y cada parte hace falta. Léanla como dos condiciones sobre VV, que tienen nombre propio:

  • Completitud. Si w∈Aw \in A, existe algún certificado cc con el que VV acepta ⟨w,c⟩\langle w, c \rangle.
  • Solidez. Si w∉Aw \notin A, VV rechaza ⟨w,c⟩\langle w, c \rangle para toda cadena cc. Ningún certificado, por ingenioso o mal formado que sea, lo convence.

Y tres observaciones.

El verificador no confía en el certificado. cc es una cadena cualquiera: puede ser basura, puede estar armada por alguien que quiere engañar. Si el verificador de HAMPATH\mathrm{HAMPATH} no revisara que los vértices no se repiten, aceptaría una lista que da vueltas por el mismo ciclo, para un grafo que no tiene ningún camino hamiltoniano, y dejaría de ser un verificador de ese lenguaje.

El certificado es corto. El tiempo se mide en ∣w∣|w|, así que un verificador de tiempo polinomial da a lo sumo p(∣w∣)p(|w|) pasos, para algún polinomio pp. En ese tiempo no puede leer más de p(∣w∣)p(|w|) símbolos de cc. Si existe un certificado, existe uno de longitud a lo sumo p(∣w∣)p(|w|): los certificados de un problema de NP tienen longitud polinomial. Un “certificado” que lista todos los caminos del grafo no cuenta.

El verificador no dice de dónde sale el certificado. La definición solo pide que exista. No hay ningún algoritmo que lo produzca, y esa es toda la gracia: NP describe los problemas donde una respuesta “sí” se puede justificar brevemente, aunque no sepamos hallar la justificación.

Idea clave. Un lenguaje está en NP si sus respuestas “sí” tienen demostraciones cortas que se comprueban rápido. El certificado es la demostración, y el verificador, quien la revisa.

Error común. Dar como “verificador” un algoritmo que busca la solución. Un programa que recibe un grafo, prueba todos los ordenamientos y responde si alguno es un camino hamiltoniano decide HAMPATH\mathrm{HAMPATH}, pero no es un verificador de tiempo polinomial: no usa ningún certificado y tarda tiempo exponencial. El verificador recibe el certificado como parte de su entrada y solo comprueba. Si en su descripción aparece “para cada subconjunto” o “probar todas las asignaciones”, no es un verificador.

Cinco problemas de NP y sus certificados

Para mostrar que un lenguaje está en NP se dan tres cosas: qué es el certificado, qué hace el verificador, y por qué corre en tiempo polinomial. Cinco ejemplos. Los cinco están programados en verifiers.h, y la salida de verify_demo que se copia en cada uno sigue a la de la sección anterior.

HAMPATH

  • Certificado: una lista de vértices p1,p2,…,pkp_1, p_2, \ldots, p_k.
  • Verificador:
V = "Con la entrada ⟨⟨G, s, t⟩, c⟩, donde G tiene m vértices:
  1. Comprobar que c es una lista de exactamente m vértices de G.
  2. Comprobar que ningún vértice se repite en la lista.
  3. Comprobar que el primero es s y el último es t.
  4. Para cada par de vértices consecutivos de la lista, comprobar que G tiene
     el arco del primero al segundo.
  5. Si todas las comprobaciones pasan, aceptar. Si alguna falla, rechazar."
  • Tiempo: el paso 2 compara a lo sumo m2m^2 pares y el paso 4 busca m−1m - 1 arcos en una lista de a lo sumo m2m^2. Polinomial en mm, y por lo tanto en la longitud de ⟨G,s,t⟩\langle G, s, t \rangle.
  • Tamaño del certificado: mm vértices, cada uno un número de ⌈log⁡2m⌉\lceil \log_2 m \rceil bits.
A la izquierda, el grafo dirigido de verify_demo: cinco vértices, con s = 1 y t = 5, y los arcos 1→2, 2→3, 3→4, 4→5, 1→3, 3→2, 2→4 y 5→1. Los arcos 1→2, 2→3, 3→4 y 4→5 están resaltados: son el camino del certificado. A la derecha, el certificado c = 1 2 3 4 5 y las cuatro comprobaciones del verificador, todas con un visto: c es una lista de 5 vértices de G; ningún vértice se repite; el primero es s y el último es t; cada paso es un arco de G. Las cuatro pasan y V acepta. Abajo, cuatro certificados que V rechaza, cada uno con la comprobación en la que falla: 1 3 4 5 falla en la 1, porque tiene 4 vértices y no 5; 1 2 2 4 5 en la 2, porque repite el vértice 2; 2 3 4 5 1 en la 3, porque es hamiltoniano pero no de s a t; 1 2 4 3 5 en la 4, porque no hay arco 4→3.A la izquierda, el grafo dirigido de verify_demo: cinco vértices, con s = 1 y t = 5, y los arcos 1→2, 2→3, 3→4, 4→5, 1→3, 3→2, 2→4 y 5→1. Los arcos 1→2, 2→3, 3→4 y 4→5 están resaltados: son el camino del certificado. A la derecha, el certificado c = 1 2 3 4 5 y las cuatro comprobaciones del verificador, todas con un visto: c es una lista de 5 vértices de G; ningún vértice se repite; el primero es s y el último es t; cada paso es un arco de G. Las cuatro pasan y V acepta. Abajo, cuatro certificados que V rechaza, cada uno con la comprobación en la que falla: 1 3 4 5 falla en la 1, porque tiene 4 vértices y no 5; 1 2 2 4 5 en la 2, porque repite el vértice 2; 2 3 4 5 1 en la 3, porque es hamiltoniano pero no de s a t; 1 2 4 3 5 en la 4, porque no hay arco 4→3.
El verificador no busca: recorre la lista que recibió y hace cuatro comprobaciones. Cada una está ahí porque algún certificado falso pasaría sin ella.

Por qué es un verificador de HAMPATH\mathrm{HAMPATH}. Si GG tiene un camino hamiltoniano de ss a tt, la lista de sus vértices pasa las cuatro comprobaciones. Y si alguna lista cc las pasa, esa lista es un camino hamiltoniano de ss a tt: tiene todos los vértices, una vez cada uno, y sus pasos son arcos. Las dos direcciones juntas dicen que VV acepta algún certificado exactamente cuando ⟨G,s,t⟩\langle G, s, t \rangle está en el lenguaje.

CLIQUE

Un clique de un grafo no dirigido es un conjunto de vértices unidos todos entre sí.

CLIQUE={ ⟨G,k⟩:G es un grafo no dirigido con un clique de k veˊrtices }\mathrm{CLIQUE} = \{\, \langle G, k \rangle : G \text{ es un grafo no dirigido con un clique de } k \text{ vértices} \,\}
  • Certificado: una lista de kk vértices.
  • Verificador: comprobar que son kk vértices de GG, que son distintos, y que para cada par de ellos GG tiene la arista que los une. Aceptar si todo pasa.
  • Tiempo: hay k(k−1)/2k(k - 1)/2 pares, con k≤mk \leq m, y cada uno se busca en la lista de aristas. Polinomial. Es la tercera pregunta de repaso de la guía.
CLIQUE: grafo no dirigido con 6 vértices y las aristas
  1-2 1-3 1-4 2-3 2-4 3-4 4-5 5-6
  k = 4
  c = 1 2 3 4       válido
  c = 4 2 1 3       válido   el orden no importa
  c = 1 2 3 5       inválido   falta la arista 1-5
  c = 1 2 3 3       inválido   repite el vértice 3
  c = 1 2 3         inválido   son 3 vértices y se pedían 4

Un detalle sobre el número kk: forma parte de la entrada, y el verificador revisa k2k^2 pares. ¿No es eso “polinomial en el valor de un número”? Aquí no hay problema, porque un clique no puede tener más vértices que el grafo: si k>mk > m el verificador rechaza sin mirar nada, y si k≤mk \leq m, entonces kk está acotado por la longitud de la entrada.

SUBSET-SUM

  • Certificado: las posiciones de los números elegidos.
  • Verificador: comprobar que las posiciones existen y son distintas, sumar los números de esas posiciones y comparar con tt.
  • Tiempo: a lo sumo nn sumas de números de la entrada. Sumar dos números de bb bits cuesta O(b)O(b): polinomial en la longitud, sin ninguna tabla que dependa del valor de tt.
SUBSET-SUM: los números 8 13 21 5 17 2, objetivo 28. El certificado son posiciones.
  c = 1 2 4 6       válido   8 + 13 + 5 + 2 = 28
  c = 3 4 6         válido   21 + 5 + 2 = 28
  c = 1 3           inválido   8 + 21 = 29
  c = 4 4 4 2       inválido   5 + 5 + 5 + 13 = 28, pero repite la posición 4
  c = 1 2 4 7       inválido   no hay posición 7

El cuarto certificado muestra por qué hay que revisar las repeticiones. Con los mismos números y objetivo 4 no hay solución: ningún subconjunto suma 4. Pero un verificador descuidado, que solo suma, aceptaría el certificado “posición 6, posición 6”, porque 2+2=42 + 2 = 4. Estaría aceptando un certificado para una instancia que no está en el lenguaje: dejaría de cumplir la solidez.

Comparen con la sección sobre la mochila. La tabla de Algoritmos decide el problema en tiempo pseudopolinomial. El verificador comprueba un certificado en tiempo polinomial de verdad. Que el problema esté en NP no depende de que los números sean pequeños.

SAT

Una fórmula booleana se arma con variables, ∧\land, ∨\lor y ¬\lnot. Una asignación le da a cada variable un valor, verdadero o falso, y satisface la fórmula si con esos valores la fórmula vale verdadero.

SAT={ ⟨φ⟩:φ es una foˊrmula booleana que alguna asignacioˊn satisface }\mathrm{SAT} = \{\, \langle \varphi \rangle : \varphi \text{ es una fórmula booleana que alguna asignación satisface} \,\}
  • Certificado: una asignación, es decir, un bit por variable.
  • Verificador: comprobar que la asignación le da un valor a cada variable de φ\varphi, reemplazar y evaluar la fórmula. Aceptar si vale verdadero.
  • Tiempo: evaluar una fórmula es un recorrido de su estructura, polinomial en su longitud.

En el código las fórmulas están en CNF, una conjunción de cláusulas, que es la forma que usan los solucionadores y la del formato DIMACS que vieron en Algoritmos. El certificado es una lista de literales: ii dice que xix_i es verdadera, y −i-i que es falsa.

SAT: φ = (x1 ∨ ¬x2) ∧ (¬x1 ∨ x2 ∨ x3) ∧ (¬x3 ∨ ¬x1). El certificado son literales.
  c = 1 2 -3        válido
  c = -3 2 1        válido   el orden no importa
  c = -1 -2 3       válido
  c = 1 -2 -3       inválido   la segunda cláusula queda falsa
  c = 1 2           inválido   x3 no tiene valor
  c = 1 -1 2 -3     inválido   x1 tiene dos valores
  c = 1 2 -4        inválido   no hay variable x4

COMPOSITES

Un número es compuesto si es el producto de dos enteros mayores que 1.

COMPOSITES={ x:x=pq para algunos enteros p,q>1 },con x en binario\mathrm{COMPOSITES} = \{\, x : x = pq \text{ para algunos enteros } p, q > 1 \,\}, \quad \text{con } x \text{ en binario}
  • Certificado: un divisor dd de xx, con 1<d<x1 < d < x.
  • Verificador: comprobar que 1<d<x1 < d < x, dividir xx entre dd y aceptar si el resto es 0.
  • Tiempo: una división de números de nn bits, que con el método de la escuela cuesta O(n2)O(n^2).
COMPOSITES: x = 8633. El certificado es un divisor.
  c = 89            válido   8633 = 89 · 97
  c = 97            válido
  c = 7             inválido   8633 = 7 · 1233 + 2
  c = 1             inválido   1 divide a todos: no demuestra nada
  c = 8633          inválido   x se divide a sí mismo: tampoco
  Con x = 8641, de los certificados 0, 1, ..., 8641 el verificador acepta 0.

Es el ejemplo más limpio de la diferencia entre encontrar y comprobar. Hallar el factor 89 probando divisores cuesta, como vimos, un tiempo exponencial en la cantidad de bits. Comprobar que 89 es un factor es una división.

La última línea es el otro lado: 8641 es primo, y el verificador rechaza todos los certificados posibles. Eso se puede comprobar por fuerza bruta porque el número es pequeño.

Este ejemplo trae además una advertencia. COMPOSITES\mathrm{COMPOSITES} está en NP, y también está en P: es el complemento de PRIMES\mathrm{PRIMES}, salvo por los números 0 y 1. Estar en NP no dice que un problema sea difícil. Dice que comprobar es fácil.

Lenguaje Certificado Bits del certificado Qué hace el verificador
HAMPATH\mathrm{HAMPATH} Una lista de los mm vértices m⌈log⁡2m⌉m \lceil \log_2 m \rceil Revisa que estén todos, una vez, de ss a tt, y cada arco
CLIQUE\mathrm{CLIQUE} kk vértices k⌈log⁡2m⌉k \lceil \log_2 m \rceil Revisa que sean distintos y cada par de ellos
SUBSET-SUM\mathrm{SUBSET\text{-}SUM} Un subconjunto de los nn números nn, con un bit por número Suma y compara con tt
SAT\mathrm{SAT} Una asignación Uno por variable Evalúa la fórmula
COMPOSITES\mathrm{COMPOSITES} Un divisor A lo sumo los de xx Divide

En C++. En verifiers.h, cada verificador es una función que recibe la instancia y el certificado y devuelve un bool. Ninguna tiene un ciclo sobre “todas las posibilidades”: los únicos ciclos recorren el certificado o la instancia. Para saber si un arco existe, verify_hampath pasa los arcos a un std::set<std::pair<int, int>>, y cada consulta cuesta O(log⁡m)O(\log m). En el laboratorio verán que esa decisión, que para la teoría no importa, separa un programa que pasa de uno que da TLE.

La otra definición: máquinas no deterministas

El nombre NP no viene de los verificadores. Viene de Nondeterministic Polynomial time: tiempo polinomial no determinista. Es la definición original, y usa la máquina de la sección El no determinismo parece costar caro.

Definición. NTIME(t(n))\mathsf{NTIME}(t(n)) es la clase de los lenguajes que decide alguna máquina de Turing no determinista que corre en tiempo O(t(n))O(t(n)).

NTIME(t(n))={ L:alguna maˊquina no determinista decide L en tiempo O(t(n)) }\mathsf{NTIME}(t(n)) = \{\, L : \text{alguna máquina no determinista decide } L \text{ en tiempo } O(t(n)) \,\}

Una máquina no determinista de tiempo polinomial para HAMPATH\mathrm{HAMPATH}:

N = "Con la entrada ⟨G, s, t⟩, donde G tiene m vértices:
  1. Escribir una lista de m números p1, ..., pm, eligiendo cada uno de forma
     no determinista entre 1 y m.
  2. Si algún número se repite, rechazar.
  3. Si p1 ≠ s o pm ≠ t, rechazar.
  4. Para cada i de 1 a m − 1: si G no tiene el arco de pi a pi+1, rechazar.
  5. Aceptar."

El paso 1 abre mmm^m ramas, una por cada lista posible. Cada rama, por separado, es corta: escribe mm números y hace las mismas comprobaciones que el verificador. La máquina acepta si alguna rama llega al paso 5, y eso pasa exactamente cuando alguna lista es un camino hamiltoniano de ss a tt. Su tiempo, que es la longitud de la rama más larga, es polinomial.

Miren los pasos 2 a 4: son el verificador de la sección anterior. Y el paso 1 es “adivinar el certificado”. No es una coincidencia.

Error común. Leer “la máquina adivina” como si tuviera suerte o inteligencia. Una máquina no determinista no elige bien: su definición de aceptar dice “existe una rama que acepta”. Es la misma idea de los NFA de la semana 2, que aceptaban si algún camino terminaba en un estado de aceptación. Nadie sabe construir un aparato que haga eso en tiempo polinomial. La máquina no determinista es una definición matemática, y no un modelo de computadora.

Las dos definiciones coinciden

Teorema. Un lenguaje tiene un verificador de tiempo polinomial si y solo si alguna máquina de Turing no determinista de tiempo polinomial lo decide. Es decir:

NP=⋃k≥1NTIME(nk)\mathsf{NP} = \bigcup_{k \geq 1} \mathsf{NTIME}(n^k)

La idea, en una frase por dirección: la máquina adivina el certificado, y el certificado es la lista de decisiones de la máquina.

Dos paneles y una franja. A la izquierda, un verificador: la entrada w y el certificado c entran a la caja V, de tiempo polinomial en |w|, que acepta o rechaza. Debajo, las dos condiciones: completitud, si w está en A existe algún c con el que V acepta ⟨w, c⟩; solidez, si w no está en A, V rechaza ⟨w, c⟩ para toda cadena c. A la derecha, la máquina no determinista para HAMPATH con el grafo de 5 vértices: de la entrada w = ⟨G, s, t⟩ salen ramas, una por cada lista que escribe el paso 1; se muestran 1 1 1 1 1, 1 2 2 4 5, 1 2 3 4 5 y 5 5 5 5 5. En cada rama, los pasos 2 a 4 son el verificador V. Tres ramas rechazan y la de 1 2 3 4 5 acepta. Son 5^5 = 3125 ramas, y como alguna acepta, N acepta w. La franja de abajo dice que «existe un certificado que V acepta» y «existe una rama de N que acepta» son el mismo «existe»: de V a N, la máquina adivina el certificado; de N a V, el certificado es la lista de decisiones de la rama.Dos paneles y una franja. A la izquierda, un verificador: la entrada w y el certificado c entran a la caja V, de tiempo polinomial en |w|, que acepta o rechaza. Debajo, las dos condiciones: completitud, si w está en A existe algún c con el que V acepta ⟨w, c⟩; solidez, si w no está en A, V rechaza ⟨w, c⟩ para toda cadena c. A la derecha, la máquina no determinista para HAMPATH con el grafo de 5 vértices: de la entrada w = ⟨G, s, t⟩ salen ramas, una por cada lista que escribe el paso 1; se muestran 1 1 1 1 1, 1 2 2 4 5, 1 2 3 4 5 y 5 5 5 5 5. En cada rama, los pasos 2 a 4 son el verificador V. Tres ramas rechazan y la de 1 2 3 4 5 acepta. Son 5^5 = 3125 ramas, y como alguna acepta, N acepta w. La franja de abajo dice que «existe un certificado que V acepta» y «existe una rama de N que acepta» son el mismo «existe»: de V a N, la máquina adivina el certificado; de N a V, el certificado es la lista de decisiones de la rama.
Las dos definiciones de NP, lado a lado. Cada rama de la máquina es el verificador corriendo con un certificado distinto.

Demostración. Por construcción, en las dos direcciones. Para fijar ideas, la entrada ⟨w,c⟩\langle w, c \rangle de un verificador se escribe w#cw\mathtt{\#}c, con un separador #\mathtt{\#} que no aparece en ww ni en cc.

De un verificador a una máquina no determinista. Sea VV un verificador de AA que da a lo sumo p(n)p(n) pasos con entradas ⟨w,c⟩\langle w, c \rangle donde ∣w∣=n|w| = n, con pp un polinomio.

Qué se construye.

N = "Con la entrada w, de longitud n:
  1. Marcar p(n) celdas. Escribir en ellas, de forma no determinista, una cadena c
     de longitud a lo sumo p(n): en cada celda, elegir un símbolo del alfabeto de
     los certificados, o terminar.
  2. Ejecutar V con la entrada ⟨w, c⟩.
  3. Si V acepta, aceptar. Si V rechaza, rechazar."

Por qué decide AA. Hay que ver que NN acepta ww si y solo si w∈Aw \in A.

  • Si NN acepta ww, alguna rama acepta. Esa rama escribió alguna cadena cc y VV aceptó ⟨w,c⟩\langle w, c \rangle. Por la definición de verificador, w∈Aw \in A.
  • Si w∈Aw \in A, VV acepta ⟨w,c⟩\langle w, c \rangle para alguna cadena cc. Falta ver que hay una así de longitud a lo sumo p(n)p(n), que es lo único que NN puede escribir. VV da a lo sumo p(n)p(n) pasos, y en cada paso el cabezal avanza a lo sumo una celda: nunca llega más allá de la celda p(n)p(n) de su cinta, así que no lee más que los primeros símbolos de cc, menos de p(n)p(n). Sea c′c' el prefijo de cc de longitud p(n)p(n), o cc entera si es más corta. Con ⟨w,c′⟩\langle w, c' \rangle, VV hace exactamente lo mismo que con ⟨w,c⟩\langle w, c \rangle, porque las dos entradas solo difieren en celdas que nunca visita. Así que VV acepta ⟨w,c′⟩\langle w, c' \rangle, y la rama de NN que escribe c′c' acepta.

Por qué es de tiempo polinomial. En cualquier rama, el paso 1 cuesta un tiempo polinomial: calcular p(n)p(n), marcar las celdas y escribir en ellas. El paso 2 da a lo sumo p(n)p(n) pasos. Todas las ramas se detienen, así que NN es un decididor, y su tiempo es polinomial.

De una máquina no determinista a un verificador. Sea NN una máquina no determinista que decide AA y cuyas ramas dan a lo sumo p(n)p(n) pasos. Sea bb la mayor cantidad de opciones que ofrece su función de transición. Para cada par de estado y símbolo, numeramos sus opciones 1,2,…1, 2, \ldots en un orden fijo. Entonces una rama de la ejecución queda descrita por la lista de números que eligió, uno por paso: una cadena sobre el alfabeto {1,…,b}\{1, \ldots, b\}.

Qué se construye.

V = "Con la entrada ⟨w, c⟩, donde c = c1 c2 ... es una cadena sobre {1, ..., b}:
  1. Simular N con la entrada w. En el paso i de la simulación, tomar la opción
     número ci de la función de transición de N.
  2. Si en algún paso la opción ci no existe, o c se acaba antes de que N se
     detenga, rechazar.
  3. Si esa rama de N acepta, aceptar. Si rechaza, rechazar."

Por qué es un verificador de AA. Hay que ver que w∈Aw \in A si y solo si VV acepta ⟨w,c⟩\langle w, c \rangle para alguna cc.

  • Si w∈Aw \in A, NN acepta ww: alguna rama termina en qacceptq_{\text{accept}}. Sea cc la lista de las opciones que esa rama eligió. Con ese cc, VV sigue esa misma rama y acepta.
  • Si VV acepta ⟨w,c⟩\langle w, c \rangle, entonces VV siguió, paso a paso, una rama real de NN con la entrada ww, y esa rama terminó en qacceptq_{\text{accept}}. Entonces NN acepta ww, y w∈Aw \in A.

Por qué es de tiempo polinomial en ∣w∣|w|. VV es determinista: cc le dice qué hacer en cada paso. Toda rama de NN se detiene en a lo sumo p(n)p(n) pasos, así que VV simula a lo sumo p(n)p(n) pasos de NN, sea cual sea la longitud de cc: si cc es más larga, lo que sobra no se lee. Con dos cintas la cuenta es directa: VV copia ww a la segunda cinta, en O(n)O(n) pasos, y queda con el primer cabezal al comienzo de cc; después, cada paso de NN es un paso de VV, que lee un símbolo de cc y avanza. Son O(n+p(n))O(n + p(n)) pasos. Esa máquina nunca mira más allá de los primeros n+1+p(n)n + 1 + p(n) símbolos de su entrada, así que pasarla a una cinta cuesta, como en el teorema de las varias cintas, a lo sumo el cuadrado: sigue siendo polinomial en ∣w∣|w|. ∎

La segunda dirección explica por qué el certificado de un problema de NP siempre puede tomarse corto: es, a lo sumo, la lista de las p(n)p(n) decisiones de una rama. Y la primera es la cuarta pregunta de repaso de la guía.

Idea clave. Las dos definiciones de NP dicen lo mismo con palabras distintas. “Existe un certificado que el verificador acepta” y “existe una rama que acepta” son el mismo “existe”. Para demostrar que un problema está en NP, casi siempre es más cómodo el verificador. Para demostrar algo sobre todos los problemas de NP, como en la semana 13, es más cómoda la máquina.

P, NP y EXPTIME

¿Dónde queda NP respecto de lo que ya tenemos? Hace falta una clase más:

EXPTIME=⋃k≥1TIME ⁣(2nk)\mathsf{EXPTIME} = \bigcup_{k \geq 1} \mathsf{TIME}\!\left(2^{n^k}\right)

Son los lenguajes que una máquina determinista decide en tiempo exponencial.

Teorema. P⊆NP⊆EXPTIME\mathsf{P} \subseteq \mathsf{NP} \subseteq \mathsf{EXPTIME}.

Demostración de P⊆NP\mathsf{P} \subseteq \mathsf{NP}. Por construcción de un verificador que no necesita el certificado. Sea A∈PA \in \mathsf{P}, y MM una máquina determinista que decide AA en tiempo polinomial.

V = "Con la entrada ⟨w, c⟩:
  1. Ignorar c. Ejecutar M con la entrada w.
  2. Si M acepta, aceptar. Si M rechaza, rechazar."

Si w∈Aw \in A, VV acepta ⟨w,c⟩\langle w, c \rangle con cualquier cc; en particular, con alguno. Si w∉Aw \notin A, VV rechaza con todos. Y VV corre en tiempo polinomial en ∣w∣|w| porque MM lo hace. Entonces VV es un verificador de tiempo polinomial de AA. ∎

Con la otra definición es todavía más corto: una máquina determinista es una máquina no determinista que nunca tiene más de una opción.

Demostración de NP⊆EXPTIME\mathsf{NP} \subseteq \mathsf{EXPTIME}. Por construcción de un decididor que prueba todos los certificados. Sea A∈NPA \in \mathsf{NP} y VV un verificador de AA que da a lo sumo p(n)p(n) pasos, con pp un polinomio. Sea Γ\Gamma el alfabeto de los certificados, con g≥2g \geq 2 símbolos.

D = "Con la entrada w, de longitud n:
  1. Para cada cadena c sobre Γ de longitud a lo sumo p(n), en orden:
  2.     Ejecutar V con la entrada ⟨w, c⟩. Si acepta, aceptar.
  3. Si ningún certificado fue aceptado, rechazar."

Decide AA: en la demostración anterior vimos que, si algún certificado sirve, alguno de longitud a lo sumo p(n)p(n) sirve. DD los prueba todos, así que acepta si y solo si w∈Aw \in A.

Tiempo: hay a lo sumo gp(n)+1g^{p(n)+1} cadenas de longitud a lo sumo p(n)p(n). Con cada una, DD ejecuta VV, que da a lo sumo p(n)p(n) pasos, y prepara la siguiente, que cuesta O(p(n))O(p(n)). El total es

O ⁣(p(n)⋅gp(n)+1)=2O(p(n)).O\!\left(p(n) \cdot g^{p(n)+1}\right) = 2^{O(p(n))}.

Si p(n)=O(nk)p(n) = O(n^k), eso es a lo sumo 2c⋅nk2^{c \cdot n^k} para alguna constante cc, que es O(2nk+1)O(2^{n^{k+1}}). Entonces A∈EXPTIMEA \in \mathsf{EXPTIME}. ∎

Esta segunda demostración es un programa que ustedes ya saben escribir: la fuerza bruta. search.h la tiene para suma de subconjuntos, tal cual: recorre los 2n2^n subconjuntos y le pasa cada uno al verificador. find_vs_check la ejecuta.

$ build/find_vs_check
Números 8 13 21 5 17 2, objetivo 28: certificado 1 2 4 6, hallado después de probar 44 de 64
Números 8 13 21 5 17 2, objetivo 4: ningún certificado sirve; se probaron los 64

Instancias sin solución: los números 2, 4, ..., 2n y un objetivo impar, cerca de la mitad de la suma
 n   certificados que prueba la búsqueda   sumas del verificador con un certificado
 4                      16                                     4
 8                     256                                     8
12                    4096                                    12
16                   65536                                    16

Con una instancia que sí tiene solución, la búsqueda puede tener suerte y detenerse antes. Con una que no la tiene, no hay atajo: para responder “no” hay que haber descartado los 2n2^n certificados. La segunda tabla usa instancias sin solución (una suma de números pares nunca es impar) y cuenta. Cada número que se agrega a la lista duplica el trabajo de la búsqueda y le suma una sola operación al verificador. Con 60 números serían 2602^{60} certificados, más de 101810^{18}. Son conteos de operaciones, no tiempos.

Esa es la distancia entre comprobar y encontrar con el único método general que conocemos. La pregunta es si existe otro.

La pregunta P contra NP

¿P=NP?\text{¿}\mathsf{P} = \mathsf{NP}\text{?}

En Algoritmos la conocieron como “¿todo problema cuya solución se comprueba rápido se puede resolver rápido?”. Con las definiciones de esta semana se puede decir sin ninguna palabra informal:

¿Es cierto que todo lenguaje que tiene un verificador de tiempo polinomial es decidido por alguna máquina de Turing determinista de tiempo polinomial?

O, con la otra definición: ¿toda máquina no determinista de tiempo polinomial tiene una determinista equivalente que también sea de tiempo polinomial? Sabemos que tiene una de tiempo exponencial. No sabemos si se puede bajar.

Qué se sabe y qué no:

  • P⊆NP⊆EXPTIME\mathsf{P} \subseteq \mathsf{NP} \subseteq \mathsf{EXPTIME}, demostrado arriba.
  • P≠EXPTIME\mathsf{P} \neq \mathsf{EXPTIME}. Es un teorema, que sale del teorema de jerarquía de tiempo de la semana 15: hay lenguajes que se deciden en tiempo exponencial y no en tiempo polinomial.
  • Por lo tanto, al menos una de las dos inclusiones es estricta. No se sabe cuál. Podría ser P=NP\mathsf{P} = \mathsf{NP}, y podría ser NP=EXPTIME\mathsf{NP} = \mathsf{EXPTIME}, aunque no las dos a la vez.
  • Casi todos los investigadores creen que P≠NP\mathsf{P} \neq \mathsf{NP}. La evidencia es de dos tipos: décadas de buscar algoritmos polinomiales para miles de problemas de NP sin encontrar ninguno, y el hecho de que bastaría encontrarlo para uno solo de los NP-completos. Pero no hay demostración.

La dificultad está en el tipo de afirmación. Para mostrar que P=NP\mathsf{P} = \mathsf{NP} bastaría un algoritmo. Para mostrar que P≠NP\mathsf{P} \neq \mathsf{NP} hay que demostrar que ninguna máquina de tiempo polinomial decide, por ejemplo, SAT\mathrm{SAT}: ni la fuerza bruta, ni ninguna idea que a alguien se le ocurra dentro de cien años. En computabilidad teníamos una herramienta para afirmaciones así, la diagonalización. La semana 15 muestra por qué esa herramienta, tal como la conocemos, no alcanza aquí.

La semana 13 retoma la pregunta desde el otro lado: los problemas NP-completos, y la demostración de que SAT\mathrm{SAT} es uno de ellos.

Lo que NP no es

NP es probablemente la sigla peor entendida de la computación. Cinco confusiones frecuentes.

NP no significa “no polinomial”. La N es de nondeterministic. Es un error grave, porque dice lo contrario de la verdad: todo problema de P está en NP. Decidir si una lista está ordenada, PATH\mathrm{PATH} y todo lenguaje regular están en NP.

NP no es “los problemas que tardan tiempo exponencial”. NP⊆EXPTIME\mathsf{NP} \subseteq \mathsf{EXPTIME} es una cota superior: dice que tiempo exponencial alcanza, y no que haga falta. De ningún problema de NP se ha demostrado que necesite tiempo exponencial. Si alguien lo hiciera, habría resuelto P≠NP\mathsf{P} \neq \mathsf{NP}.

Estar en NP no es ser difícil. NP es una cota superior de dificultad. Los problemas difíciles de NP son los NP-completos, que son otra cosa: los más difíciles dentro de NP. COMPOSITES\mathrm{COMPOSITES} está en NP y también en P.

NP es una clase de problemas de decisión. “Hallar el camino hamiltoniano más corto” no es un lenguaje, y no está ni deja de estar en NP. Lo que se clasifica es la versión con respuesta sí o no. En la semana 1 se vio por qué eso no pierde generalidad.

El certificado solo existe para las respuestas “sí”. Esta es la más sutil, y merece su propia sección.

coNP: el lado del no

La definición de verificador es asimétrica. Si w∈Aw \in A, pide que exista un certificado. Si w∉Aw \notin A, no pide ninguna justificación: solo que nada convenza al verificador. Para SAT\mathrm{SAT}:

  • ¿Qué probaría que una fórmula tiene una asignación que la satisface? La asignación. Es corta, y se comprueba evaluando.
  • ¿Qué probaría que una fórmula no tiene ninguna?

Piénsenlo un momento antes de seguir. Mostrar una asignación que falla no prueba nada: puede haber otra que funcione. Mostrar que fallan mil tampoco. Lo único evidente es la lista de las 2m2^m asignaciones de las mm variables, con la comprobación de que todas fallan, y esa lista no tiene longitud polinomial. La fórmula de ejemplo example_unsatisfiable, con las cuatro cláusulas posibles sobre dos variables, no tiene solución: las pruebas lo comprueban revisando sus 4 asignaciones. Con 300 variables no hay universo que alcance para la lista.

No se conoce ningún certificado corto de que una fórmula no tiene solución. Y no se ha demostrado que no exista.

Definición. 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} \,\}

Dicho con certificados: en un lenguaje de coNP, las respuestas “no” son las que tienen demostraciones cortas. El complemento de SAT\mathrm{SAT} está en coNP por definición, igual que el complemento de HAMPATH\mathrm{HAMPATH}: los grafos que no tienen camino hamiltoniano. La pregunta de arriba es si SAT‾\overline{\mathrm{SAT}} está también en NP, y es la quinta pregunta de repaso de la guía: no es evidente, porque no se ve qué podría servir de certificado.

Error común. Creer que coNP es el complemento de NP, es decir, “los lenguajes que no están en NP”. No lo es. coNP es la clase de los complementos de los lenguajes de NP. Las dos clases se solapan: todo lenguaje de P está en las dos.

¿Por qué no basta intercambiar aceptar y rechazar? Con las máquinas deterministas ese truco funciona: si MM decide AA en tiempo polinomial, la máquina que hace lo mismo y responde al revés decide A‾\overline{A} en el mismo tiempo. Por eso P es cerrada bajo complemento, y de ahí sale que

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

Con una máquina no determinista NN el truco falla, y vale la pena ver dónde. Sea N′N' la máquina que resulta de intercambiar qacceptq_{\text{accept}} y qrejectq_{\text{reject}} en NN. Entonces N′N' acepta ww si alguna rama de NN rechaza. Pero w∉L(N)w \notin L(N) significa que todas las ramas de NN rechazan. Si NN es la máquina que adivina una asignación y la evalúa, N′N' acepta las fórmulas que tienen alguna asignación que falla, que son casi todas, y no las que no tienen solución. Es lo mismo que pasaba con los NFA en la semana 2: cambiar los estados de aceptación de un NFA no da el complemento.

El “existe” de la definición de NP se convierte, al complementar, en un “para todo”. NP es la clase de los problemas de la forma “existe un cc corto tal que…”, y coNP la de los problemas “para todo cc corto…”.

Lo que se sabe:

  • P⊆NP∩coNP\mathsf{P} \subseteq \mathsf{NP} \cap \mathsf{coNP}.
  • Si P=NP\mathsf{P} = \mathsf{NP}, entonces NP=coNP\mathsf{NP} = \mathsf{coNP}: P es cerrada bajo complemento, así que NP también lo sería. Al revés: si alguien demuestra que NP≠coNP\mathsf{NP} \neq \mathsf{coNP}, demuestra que P≠NP\mathsf{P} \neq \mathsf{NP}.
  • No se sabe si NP=coNP\mathsf{NP} = \mathsf{coNP}. Se cree que no.

Hay problemas que están en las dos clases sin que eso sea evidente. PRIMES\mathrm{PRIMES} está en coNP, porque su complemento es en esencia COMPOSITES\mathrm{COMPOSITES}: un divisor certifica que un número no es primo. Mucho antes de saberse que está en P, se demostró que también está en NP: existe un certificado corto de que un número sí es primo, aunque es bastante menos obvio que un divisor.

Dos mapas de clases, uno junto al otro, y una franja debajo. A la izquierda, lo que se cree, P ≠ NP y NP ≠ coNP: dentro de EXPTIME se cruzan NP y coNP. En la parte de NP que queda fuera del cruce están los NP-completos SAT, HAMPATH, CLIQUE y SUBSET-SUM, que la semana 13 y el curso de Algoritmos demuestran NP-completos; en la parte de coNP, sus complementos. En el cruce, NP ∩ coNP, está P, con PATH, los lenguajes libres de contexto, PRIMES y COMPOSITES. Fuera de P hay lenguajes de EXPTIME, y eso es un teorema. A la derecha, lo que pasaría si P = NP: dentro de EXPTIME hay una sola clase, P = NP = coNP, con todos esos problemas y sus complementos, y fuera de ella sigue habiendo algo. La franja dice que P ⊆ NP ∩ coNP, NP ⊆ EXPTIME y P ≠ EXPTIME están demostrados y valen en los dos dibujos, y que no se sabe cuál es el verdadero.Dos mapas de clases, uno junto al otro, y una franja debajo. A la izquierda, lo que se cree, P ≠ NP y NP ≠ coNP: dentro de EXPTIME se cruzan NP y coNP. En la parte de NP que queda fuera del cruce están los NP-completos SAT, HAMPATH, CLIQUE y SUBSET-SUM, que la semana 13 y el curso de Algoritmos demuestran NP-completos; en la parte de coNP, sus complementos. En el cruce, NP ∩ coNP, está P, con PATH, los lenguajes libres de contexto, PRIMES y COMPOSITES. Fuera de P hay lenguajes de EXPTIME, y eso es un teorema. A la derecha, lo que pasaría si P = NP: dentro de EXPTIME hay una sola clase, P = NP = coNP, con todos esos problemas y sus complementos, y fuera de ella sigue habiendo algo. La franja dice que P ⊆ NP ∩ coNP, NP ⊆ EXPTIME y P ≠ EXPTIME están demostrados y valen en los dos dibujos, y que no se sabe cuál es el verdadero.
Los dos mundos posibles. Lo demostrado vale en ambos; lo que nadie sabe es si la frontera entre P y NP existe.

La semana 13 vuelve a coNP con más herramientas.

En la práctica. Los solucionadores SAT viven esta asimetría. Cuando responden “satisfacible”, entregan la asignación, y cualquiera la comprueba en un instante con un verificador como el del laboratorio. Cuando responden “insatisfacible”, lo más que pueden entregar es un registro de su razonamiento, paso por paso, para que otro programa lo revise. Ese registro es un certificado, pero no es corto: en problemas difíciles ocupa gigabytes.

El código de la semana

code/week-12/
├── tm.h                  struct Tm, lectura del formato .tm y ejecución contando pasos
├── multitape.h           máquina de k cintas, y la de dos cintas para 0^k 1^k
├── run_tm.cpp            ejecuta una máquina .tm: veredicto, pasos y configuraciones
├── count_steps.cpp       las dos tablas de pasos de las tres máquinas
├── encoding_demo.cpp     binario y unario; divisiones de prueba; la tabla de SUBSET-SUM
├── verifiers.h           los cinco verificadores: HAMPATH, CLIQUE, SUBSET-SUM, SAT, COMPOSITES
├── search.h              búsqueda exhaustiva, tabla de sumas y divisiones de prueba
├── examples.h            las instancias de ejemplo de este capítulo
├── verify_demo.cpp       cada verificador con certificados buenos, malos y mal formados
├── find_vs_check.cpp     cuántos certificados prueba la búsqueda y cuánto cuesta comprobar uno
├── machines/             las dos máquinas de una cinta, en formato .tm
├── errors/               el intento de una sola pasada, que no decide el lenguaje
├── test_time.cpp         las máquinas deciden 0^k 1^k; fórmulas y tablas de pasos
├── test_encoding.cpp     longitudes en binario, divisiones y casillas de la tabla
├── test_verifiers.cpp    los certificados del capítulo; existe certificado si y solo si la respuesta es sí
└── lab/verifiers/        el laboratorio: tres verificadores

make compila todo, y make test corre las pruebas con ASan y UBSan. Las pruebas comprueban con assert lo que este capítulo afirma. test_time compara las tres máquinas con una función de C++ que decide { 0k1k }\{\, \mathtt{0}^k\mathtt{1}^k \,\} mirando la cadena, sobre las 8191 cadenas de longitud a lo sumo 12; comprueba el peor caso de cada longitud, las fórmulas exactas de pasos, las cotas de las demostraciones y cada número de las tablas. test_encoding comprueba las longitudes en binario, las divisiones de la tabla de primos y las casillas de la tabla de sumas, y que la tabla y la búsqueda exhaustiva deciden lo mismo en 300 instancias al azar. test_verifiers comprueba cada certificado copiado en este capítulo y, en instancias pequeñas, la definición de NP completa: para HAMPATH\mathrm{HAMPATH}, que el verificador acepta algún ordenamiento exactamente cuando un algoritmo independiente dice que el camino existe.

$ make test
test_time: ok (3 máquinas, 8191 cadenas cada una)
test_encoding: ok
test_verifiers: ok
Todas las pruebas pasaron.

Los archivos de máquinas son:

Archivo Qué hace Estados, sin los finales Tiempo
machines/zeros_ones_quadratic.tm Decide { 0k1k }\{\, \mathtt{0}^k\mathtt{1}^k \,\} emparejando de uno en uno 4 O(n2)O(n^2)
machines/zeros_ones_nlogn.tm Decide el mismo lenguaje tachando uno de cada dos 9 O(nlog⁡n)O(n \log n)
errors/zeros_ones_one_pass.tm Solo comprueba la forma 0∗1∗\mathtt{0}^*\mathtt{1}^*: no decide el lenguaje 2 O(n)O(n)

Para experimentar, usen run_tm con sus propias cadenas, y con --watch y el nombre de un estado para ver la cinta cada vez que la máquina entra en él. Es el mismo formato .tm de su simulador de la semana 7: pueden correr estas máquinas ahí y comparar la cantidad de pasos.

En tm.h, δ\delta es un std::map con los nombres de los estados, para que el struct se lea como la definición. Antes de ejecutar, run_tm la pasa a una tabla indexada por números: con 33 millones de pasos, buscar nombres en un mapa en cada uno se nota.

El laboratorio

En lab/verifiers hay tres problemas, cada uno en su carpeta: hampath, sat y subset_sum. En los tres, el programa lee una instancia y varios certificados, y responde válido o inválido por cada uno.

cd lab/verifiers/subset_sum
make        # compila solution.cpp
make test   # corre el juez con todos los casos

Son los verificadores de este capítulo, con dos exigencias más. La primera es la de la definición, tomada en serio: rechazar los certificados mal formados. Los casos traen vértices repetidos, variables sin valor, índices fuera de rango y cantidades equivocadas. La segunda no es de la definición sino del juez: los casos grandes piden un verificador de tiempo lineal o casi lineal. Un verificador cuadrático sigue siendo un verificador de tiempo polinomial, pero da TLE. En suma de subconjuntos, además, los números llegan a 101310^{13} y las sumas a 5⋅10185 \cdot 10^{18}: no caben en un int, y sí en un long long.

El enunciado general, con las preguntas que deben responder, está en lab/verifiers/README.md.

Resumen

  • Desde esta semana todas las máquinas son decididores. La pregunta es cuántos pasos dan.
  • El tiempo de una máquina determinista es f(n)f(n): el máximo número de pasos sobre las entradas de longitud nn. TIME(t(n))\mathsf{TIME}(t(n)) es la clase de los lenguajes que una máquina determinista de una cinta decide en tiempo O(t(n))O(t(n)). Es una clase de lenguajes, no de máquinas.
  • Para { 0k1k }\{\, \mathtt{0}^k\mathtt{1}^k \,\}: emparejar de uno en uno cuesta O(n2)O(n^2); tachar uno de cada dos y comparar paridades, O(nlog⁡n)O(n \log n), que es lo mejor con una cinta; con dos cintas, O(n)O(n). El costo exacto depende del modelo.
  • Una máquina de varias cintas de tiempo t(n)t(n) se simula en una cinta en tiempo O(t(n)2)O(t(n)^2): t(n)t(n) pasos, y cada uno cuesta recorrer O(t(n))O(t(n)) celdas.
  • P=⋃kTIME(nk)\mathsf{P} = \bigcup_k \mathsf{TIME}(n^k). Como el cuadrado de un polinomio es un polinomio, P no cambia con la cantidad de cintas, ni con ningún otro modelo determinista razonable. Por eso se puede describir en alto nivel: etapas polinomiales, cada una de costo polinomial.
  • El tiempo se mide contra la longitud de la entrada, y los números se escriben en binario. Un algoritmo que da xx pasos para el número xx es exponencial. Un algoritmo pseudopolinomial, como la tabla de la mochila, es polinomial en el valor de los números y no en su longitud.
  • PATH\mathrm{PATH} está en P, y todo lenguaje libre de contexto también, por CYK con la gramática fija.
  • Una máquina no determinista de tiempo t(n)t(n) se simula de forma determinista en tiempo 2O(t(n))2^{O(t(n))}. No se conoce nada mejor.
  • Un verificador de AA es un algoritmo VV tal que w∈Aw \in A si y solo si VV acepta ⟨w,c⟩\langle w, c \rangle para algún certificado cc. Su tiempo se mide en ∣w∣|w|. NP es la clase de los lenguajes con verificador de tiempo polinomial. Los certificados tienen longitud polinomial, y el verificador rechaza los que están mal formados.
  • NP=⋃kNTIME(nk)\mathsf{NP} = \bigcup_k \mathsf{NTIME}(n^k): la máquina adivina el certificado, y el certificado es la lista de decisiones de la máquina.
  • HAMPATH\mathrm{HAMPATH}, CLIQUE\mathrm{CLIQUE}, SUBSET-SUM\mathrm{SUBSET\text{-}SUM}, SAT\mathrm{SAT} y COMPOSITES\mathrm{COMPOSITES} están en NP. Sus certificados: un camino, un conjunto de vértices, un subconjunto, una asignación, un divisor.
  • P⊆NP⊆EXPTIME\mathsf{P} \subseteq \mathsf{NP} \subseteq \mathsf{EXPTIME}. Un decididor es un verificador que ignora el certificado, y probar todos los certificados cuesta tiempo exponencial. Como P≠EXPTIME\mathsf{P} \neq \mathsf{EXPTIME}, alguna de las dos inclusiones es estricta. No se sabe cuál: esa es la pregunta P\mathsf{P} contra NP\mathsf{NP}.
  • NP no es “no polinomial”, ni “exponencial”, ni “difícil”. Y sus certificados son solo para las respuestas “sí”.
  • coNP\mathsf{coNP} es la clase de los lenguajes cuyo complemento está en NP: los que tienen certificados cortos para el “no”. P⊆NP∩coNP\mathsf{P} \subseteq \mathsf{NP} \cap \mathsf{coNP}. No se sabe si NP=coNP\mathsf{NP} = \mathsf{coNP}; intercambiar aceptar y rechazar en una máquina no determinista no da el complemento.

Ejercicios

  1. Para cada función, digan si es O(n2)O(n^2), si es O(n3)O(n^3), si es 2O(n)2^{O(n)} y si es polinomial: (a) 5n2+3nlog⁡2n5n^2 + 3n \log_2 n; (b) n2log⁡2nn^2 \log_2 n; (c) 23n2^{3n}; (d) 3n3^n; (e) nlog⁡2nn^{\log_2 n}; (f) 2(log⁡2n)22^{(\log_2 n)^2}. Dos de ellas son la misma función: ¿cuáles? ¿Es cierto que 3n=O(2n)3^n = O(2^n)? ¿Y que 3n=2O(n)3^n = 2^{O(n)}?
  2. Sigan a mano la máquina machines/zeros_ones_nlogn.tm con la entrada 000111\mathtt{000111}: escriban la cinta al final de cada pasada y el estado en que la máquina llega al blanco. Comprueben con build/run_tm machines/zeros_ones_nlogn.tm --watch back 000111. ¿Cuántos pasos da? Compárenlo con la fórmula del capítulo. Después hagan lo mismo con 0000001111\mathtt{0000001111} y digan en qué pasada rechaza y por qué.
  3. Den una descripción de implementación de una máquina de una cinta que decida { w#w:w∈{0,1}∗ }\{\, w\mathtt{\#}w : w \in \{\mathtt{0}, \mathtt{1}\}^* \,\} y demuestren que corre en tiempo O(n2)O(n^2). Después den una de dos cintas que lo decida en O(n)O(n). ¿Qué cota da el teorema de simulación para la segunda, pasada a una cinta?
  4. Para programar. Escriban en formato .tm una máquina que decida { akbkck:k≥0 }\{\, \mathtt{a}^k\mathtt{b}^k\mathtt{c}^k : k \geq 0 \,\} con la idea de tachar uno de cada dos, y midan sus pasos con run_tm para k=4,8,16,32,64k = 4, 8, 16, 32, 64. ¿Cuánto crece al duplicar kk? Agreguen una prueba que la compare con una función de C++ en todas las cadenas de longitud a lo sumo 9 sobre {a,b,c}\{\mathtt{a}, \mathtt{b}, \mathtt{c}\}.
  5. En la demostración de que varias cintas se simulan en O(t(n)2)O(t(n)^2): (a) ¿dónde se usa que t(n)≥nt(n) \geq n? (b) ¿Por qué cada tramo de la cinta de SS tiene a lo sumo t(n)+1t(n) + 1 celdas? (c) Si MM tiene kk cintas, ¿cuántos desplazamientos puede hacer falta al simular un solo paso, y cuánto cuesta cada uno? (d) El teorema da una cota superior. Den un ejemplo del capítulo donde la máquina de una cinta que sale de la simulación no es la más rápida posible para ese lenguaje.
  6. Un algoritmo recibe un número xx en binario y calcula x!x! con un ciclo de xx multiplicaciones. ¿Es de tiempo polinomial? Den dos razones distintas por las que no: una sobre la cantidad de vueltas y otra sobre el tamaño del resultado. ¿Cuántos bits tiene, aproximadamente, x!x!?
  7. Sea UNARY-SSUM\mathrm{UNARY\text{-}SSUM} el lenguaje de suma de subconjuntos con todos los números escritos en unario. Demuestren que está en P, con el patrón del capítulo: el algoritmo, por qué es correcto y la cuenta del tiempo en función de la longitud de la entrada. ¿Por qué la misma demostración no sirve para SUBSET-SUM\mathrm{SUBSET\text{-}SUM}?
  8. Demuestren que P es cerrada bajo unión, intersección, complemento y concatenación. Para la concatenación: dadas máquinas de tiempo polinomial para AA y BB, describan una para ABAB y cuenten cuántas veces llama a cada una. Después demuestren que NP es cerrada bajo unión e intersección, con verificadores. ¿Qué pasa cuando intentan lo mismo con el complemento?
  9. Demuestren que estos lenguajes están en NP, dando el certificado, el verificador y su tiempo: (a) { ⟨G,k⟩:G tiene un conjunto independiente de k veˊrtices }\{\, \langle G, k \rangle : G \text{ tiene un conjunto independiente de } k \text{ vértices} \,\}; (b) { ⟨G⟩:G se puede colorear con 3 colores }\{\, \langle G \rangle : G \text{ se puede colorear con 3 colores} \,\}; (c) { ⟨G,H⟩:G y H son grafos isomorfos }\{\, \langle G, H \rangle : G \text{ y } H \text{ son grafos isomorfos} \,\}. En cada uno, digan cuántos bits tiene el certificado y den un certificado mal formado que su verificador deba rechazar.
  10. Alguien propone este “verificador” para SUBSET-SUM\mathrm{SUBSET\text{-}SUM}: “Con la entrada ⟨⟨S,t⟩,c⟩\langle \langle S, t \rangle, c \rangle: ignorar cc; llenar la tabla de sumas alcanzables; aceptar si tt es alcanzable.” (a) ¿Cumple que acepta algún cc si y solo si la instancia está en el lenguaje? (b) ¿Es un verificador de tiempo polinomial? (c) Otra persona propone: “sumar los números de las posiciones que dice cc y aceptar si dan tt”, sin revisar nada más. Den una instancia que no está en el lenguaje y un certificado que este segundo verificador acepta.
  11. En la demostración de que un verificador da una máquina no determinista, se usó que basta adivinar certificados de longitud a lo sumo p(n)p(n). (a) Escriban ese argumento con sus palabras. (b) ¿Qué saldría mal si la definición de verificador midiera el tiempo en función de ∣⟨w,c⟩∣|\langle w, c \rangle| y no de ∣w∣|w|? Muestren que, con esa definición, ATMA_{\mathrm{TM}} tendría un “verificador de tiempo polinomial”, tomando como certificado la historia de cómputo de la semana 10.
  12. Demuestren: (a) si P=NP\mathsf{P} = \mathsf{NP}, entonces NP=coNP\mathsf{NP} = \mathsf{coNP}; (b) coNP⊆EXPTIME\mathsf{coNP} \subseteq \mathsf{EXPTIME}; (c) un lenguaje AA está en coNP si y solo si existe un algoritmo VV de tiempo polinomial en ∣w∣|w| tal que w∈Aw \in A exactamente cuando VV acepta ⟨w,c⟩\langle w, c \rangle para toda cadena cc de longitud a lo sumo p(∣w∣)p(|w|). Usen (c) para decir qué “verifica” el verificador de SAT‾\overline{\mathrm{SAT}}.
  13. Para programar. Agreguen a search.h una búsqueda exhaustiva para HAMPATH\mathrm{HAMPATH} que pruebe los ordenamientos con std::next_permutation y llame a verify_hampath, contando cuántos prueba. Midan con grafos sin camino hamiltoniano de 6, 8 y 10 vértices (por ejemplo, un grafo con un vértice sin arcos de entrada distinto de ss). ¿Cómo crece? Compárenlo con el crecimiento de la búsqueda de suma de subconjuntos. ¿Cuál de los dos certificados tiene más bits, y cómo se relaciona eso con la cantidad de candidatos?