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

Apuntes · Capítulo 15Complejidad

Jerarquías, azar y lo que sigue abierto

Jerarquías, azar y lo que sigue abierto

La semana pasada terminó con una cadena de clases, cada una dentro de la siguiente:

L⊆NL⊆P⊆NP⊆PSPACE⊆EXPTIME.\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{P} \subseteq \mathsf{NP} \subseteq \mathsf{PSPACE} \subseteq \mathsf{EXPTIME}.

Cada inclusión tiene su demostración, y todas son del mismo tipo: una simulación. Lo que no tenemos es lo contrario. Para ninguna de las cinco inclusiones hemos demostrado que sea estricta, es decir, que la clase de la derecha tenga algún lenguaje que la de la izquierda no tiene. Con lo que sabemos hasta hoy, las seis clases podrían ser la misma.

Eso no puede ser, y esta semana se demuestra. La herramienta es la más vieja del curso: la diagonalización de la semana 9, la que mostró que ATMA_{\mathrm{TM}} es indecidible. Ahora la diagonal lleva un reloj y una cinta medida, y el resultado son los teoremas de jerarquía: con más espacio, o con más tiempo, se decide estrictamente más. De ahí sale que P≠EXPTIME\mathsf{P} \neq \mathsf{EXPTIME} y que NL≠PSPACE\mathsf{NL} \neq \mathsf{PSPACE}. Son las únicas separaciones de la cadena que se conocen, y veremos también por qué esta técnica, sola, no puede dar las que faltan.

La segunda mitad agrega un recurso que hasta aquí no habíamos usado: el azar. Una máquina que lanza monedas puede comprobar si A⋅B=CA \cdot B = C sin multiplicar las matrices, y equivocarse con una probabilidad tan pequeña como se quiera. Eso da una clase nueva, BPP, y la última pregunta del curso: si el azar permite resolver algo que sin él no se puede resolver en tiempo polinomial.

Esta es la última semana de clases. El capítulo cierra con lo que sigue abierto, con lo que queda fuera del curso, y con el mapa completo: de los lenguajes regulares a los que ninguna máquina reconoce, con un lenguaje que separa cada nivel y la técnica que lo demuestra.

Ruta de lectura.

Antes de clase (15–20 minutos): la introducción, Lo que la cadena no dice y La diagonal, otra vez. Antes de la sesión B, Máquinas que lanzan monedas. Con eso llegan con la pregunta de cada sesión y con la tabla de la diagonal recordada.

En clase: Sesión A, de Lo que la cadena no dice a Oráculos y los límites de la diagonalización. Sesión B, de Máquinas que lanzan monedas a El mapa completo del curso.

Después de clase: el Resumen y los Ejercicios. Antes del laboratorio, Verificar un producto sin multiplicar, Repetir para bajar el error y El código de la semana. Para preparar el examen final, El mapa completo del curso. La sección Oráculos y los límites de la diagonalización es opcional (✂️): se puede saltar sin perder el hilo.

Lectura. Sipser, sec. 9.1 (Hierarchy Theorems) y 9.2 (Relativization) para la sesión A, y sec. 10.2 (Probabilistic Algorithms) para la sesión B. Barak, capítulos 19 (Probabilistic computation) y 20 (Modeling randomized computation). Son apoyo: estos apuntes se pueden estudiar solos.

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

Lo que la cadena no dice

Repasemos de dónde salió cada eslabón.

Inclusión Por qué vale Semana
L⊆NL\mathsf{L} \subseteq \mathsf{NL} Una máquina determinista es una no determinista que nunca elige 14
NL⊆P\mathsf{NL} \subseteq \mathsf{P} Una máquina de espacio logarítmico tiene una cantidad polinomial de configuraciones, y aceptar es alcanzar una de ellas en ese grafo 14
P⊆NP\mathsf{P} \subseteq \mathsf{NP} Lo mismo que en la primera fila, ahora con tiempo 12
NP⊆PSPACE\mathsf{NP} \subseteq \mathsf{PSPACE} Se prueban los certificados uno por uno, reutilizando el espacio 14
PSPACE⊆EXPTIME\mathsf{PSPACE} \subseteq \mathsf{EXPTIME} Con espacio f(n)f(n) hay a lo sumo 2O(f(n))2^{O(f(n))} configuraciones, y una máquina que se detiene no repite ninguna 14

Aquí EXPTIME\mathsf{EXPTIME} es la clase de los lenguajes que se deciden en tiempo exponencial:

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

Las cinco filas tienen la misma forma: “lo que hace una máquina del primer tipo lo puede hacer una del segundo”. Ninguna dice “y la del segundo tipo hace algo que la del primero no puede”. Para afirmar eso hay que exhibir un lenguaje y demostrar que ninguna máquina del primer tipo lo decide. Es un enunciado sobre todas las máquinas posibles, también las que a nadie se le han ocurrido.

Ya hicimos algo así una vez. En la semana 9 demostramos que ninguna máquina de Turing decide ATMA_{\mathrm{TM}}. No revisamos las máquinas una por una: construimos una máquina DD que, puesta frente a cualquier otra, hace lo contrario que ella en al menos una entrada. Esta semana se repite la jugada, con una diferencia. Entonces bastaba con que DD fuera distinta de todas las máquinas. Ahora DD tiene que ser distinta de todas las máquinas que usan pocos recursos, y además tiene que usar ella misma una cantidad de recursos conocida. Si lo logramos, el lenguaje de DD queda en la clase grande y fuera de la pequeña.

Idea clave. Una inclusión se demuestra con una simulación: una máquina imita a otra. Una separación pide más: un lenguaje y un argumento sobre todas las máquinas de una clase. La única técnica del curso que produce un argumento así es la diagonalización.

La diagonal, otra vez

Recordemos el argumento en su forma más simple, sobre una lista finita y concreta. Tomemos seis máquinas que siempre se detienen y las seis primeras cadenas binarias, en el orden de la semana 1. El programa diagonal_demo arma la tabla de respuestas: una fila por máquina, una columna por cadena, A si acepta y R si rechaza.

$ build/diagonal_demo
                         ε    0    1   00   01   10
M1: acepta todo         [A]   A    A    A    A    A 
M2: no acepta nada       R   [R]   R    R    R    R 
M3: longitud par         A    R   [R]   A    A    A 
M4: termina en 1         R    R    A   [R]   A    R 
M5: contiene un 0        R    A    R    A   [A]   A 
M6: empieza con 1        R    R    A    R    R   [A]
D: lo contrario          R    A    A    A    R    R 

D y M1 responden distinto con la cadena ε.
D y M2 responden distinto con la cadena 0.
D y M3 responden distinto con la cadena 1.
D y M4 responden distinto con la cadena 00.
D y M5 responden distinto con la cadena 01.
D y M6 responden distinto con la cadena 10.

Las casillas entre corchetes son la diagonal: lo que la máquina ii responde con la cadena ii. La última fila se arma cambiando cada casilla de la diagonal. Esa fila no puede ser igual a ninguna de las seis, porque difiere de la fila ii justo en la columna ii. No hizo falta saber qué hace cada máquina: solo poder preguntarle.

En la semana 9 la lista era infinita, la de todas las máquinas de Turing, y la cadena número ii era la descripción ⟨Mi⟩\langle M_i \rangle de la máquina número ii. El argumento era el mismo, y tenía un precio que conviene mirar con cuidado, porque es todo el tema de hoy:

Para llenar su fila, DD tiene que averiguar qué responde cada máquina. Es decir, tiene que simularla.

En la semana 9 eso era un problema sin salida: la máquina simulada podía no detenerse, y por eso el argumento terminaba en una contradicción y no en una máquina DD de verdad. Hoy las máquinas de la lista tienen un límite de recursos. Una máquina que usa a lo sumo f(n)f(n) celdas se puede simular hasta el final con un poco más de f(n)f(n) celdas. Entonces DD sí existe, y lo que el argumento entrega ya no es una contradicción: es un lenguaje que DD decide con sus recursos y que ninguna máquina más pobre decide.

Quedan tres detalles por resolver, y cada uno deja una marca en el enunciado del teorema.

  1. DD tiene que saber cuánto es f(n)f(n) para ponerse el límite, y calcularlo no puede costarle más que el propio límite. Eso es pedir que ff sea construible.
  2. Simular cuesta un poco más que lo simulado. Por eso el teorema separa O(f(n))O(f(n)) de o(f(n))o(f(n)), y no f(n)f(n) de f(n)−1f(n) - 1.
  3. “Poco espacio” es una promesa para entradas grandes. Para que DD se enfrente a cada máquina con una entrada lo bastante grande, cada máquina tiene que aparecer en la lista muchas veces. Eso se resuelve con un relleno.

Funciones construibles

Antes de los teoremas, dos convenciones.

El modelo. El espacio se mide como en la semana 14, con una cinta de entrada de solo lectura y una cinta de trabajo, y solo cuenta la cinta de trabajo. Así tienen sentido las cotas menores que nn. Todas las funciones ff de esta sección cumplen f(n)≥log⁡2nf(n) \geq \log_2 n.

La notación oo. Decimos que g(n)=o(f(n))g(n) = o(f(n)) si gg crece estrictamente más lento que ff: para toda constante c>0c > 0 existe un n0n_0 tal que g(n)<c⋅f(n)g(n) < c \cdot f(n) para todo n≥n0n \geq n_0. Es más fuerte que g(n)=O(f(n))g(n) = O(f(n)), que solo pide alguna constante. Por ejemplo, n=o(nlog⁡n)n = o(n \log n) y log⁡2n=o(n)\log^2 n = o(n), pero 3n3n no es o(n)o(n).

Una función f:N→Nf : \mathbb{N} \to \mathbb{N}, con f(n)≥log⁡2nf(n) \geq \log_2 n, es construible en espacio (space constructible) si alguna máquina de Turing, con la entrada 1n\mathtt{1}^n, escribe f(n)f(n) en binario usando espacio O(f(n))O(f(n)).

En palabras: se puede averiguar cuánto espacio es f(n)f(n) sin gastar más que eso. Todas las funciones que uno escribe al medir un algoritmo lo son: log⁡2n\log_2 n, nn, nlog⁡2nn \log_2 n, n2n^2, nkn^k, 2n2^n. Para n2n^2, por ejemplo, la máquina cuenta los unos de la entrada en binario, que ocupa O(log⁡n)O(\log n) celdas, y multiplica ese número por sí mismo, que ocupa otras O(log⁡n)O(\log n).

¿Por qué hace falta la condición? Porque la máquina DD va a empezar marcando f(n)f(n) celdas de su cinta, para no pasarse de ahí. Si calcular f(n)f(n) exigiera más espacio que f(n)f(n), la propia DD ya no cabría en la clase donde queremos ponerla. Y sin la condición el teorema es falso: existen funciones raras, que no son construibles, para las que dar más espacio no agrega ningún lenguaje. No las veremos; alcanza con saber que la hipótesis no es un adorno.

Para el tiempo la definición es la misma, cambiando el recurso. Una función tt, con t(n)≥nlog⁡2nt(n) \geq n \log_2 n, es construible en tiempo (time constructible) si alguna máquina, con la entrada 1n\mathtt{1}^n, escribe t(n)t(n) en binario en tiempo O(t(n))O(t(n)).

El teorema de jerarquía de espacio

Teorema (jerarquía de espacio). Para toda función ff construible en espacio existe un lenguaje AA que se decide en espacio O(f(n))O(f(n)) y que no se decide en espacio o(f(n))o(f(n)).

Con más espacio se decide estrictamente más, y basta con muy poco más: cualquier cantidad que no sea un múltiplo constante.

El primer intento, y dónde falla

Copiemos la semana 9 sin pensar. Sea DD la máquina que, con la entrada ⟨M⟩\langle M \rangle, simula a MM con la entrada ⟨M⟩\langle M \rangle usando a lo sumo f(n)f(n) celdas, y responde lo contrario. Si la simulación quiere más celdas, DD rechaza.

Esta DD usa espacio O(f(n))O(f(n)), y eso está bien. El problema aparece al comparar. Supongamos que una máquina MM decide el lenguaje de DD en espacio g(n)=o(f(n))g(n) = o(f(n)), y démosle a DD la entrada ⟨M⟩\langle M \rangle. Quisiéramos decir: ”DD simula a MM hasta el final y responde lo contrario, contradicción”. Fallan dos cosas.

  • La simulación puede no caber. Que g(n)=o(f(n))g(n) = o(f(n)) dice que gg es menor que ff para nn grande. Para la longitud concreta de ⟨M⟩\langle M \rangle no dice nada. Y DD ni siquiera simula con g(n)g(n) celdas: usa algunas más, como veremos. Si no cabe, DD rechaza sin haber terminado la simulación, y que MM también rechace no contradice nada.
  • MM podría no detenerse. A DD le llega la descripción de cualquier máquina, también de una que entra en un ciclo sin salir de sus primeras tres celdas. El límite de espacio no la detiene nunca, y DD tiene que detenerse siempre: si no, no decide ningún lenguaje.

Cada falla tiene su arreglo.

La máquina D

D = "Con la entrada w:
  1. Sea n la longitud de w.
  2. Calcular f(n) y marcar f(n) celdas de la cinta de trabajo.
     Si alguna etapa posterior intenta salir de las celdas marcadas, rechazar.
  3. Si w no tiene la forma ⟨M⟩10* para alguna máquina de Turing M, rechazar.
  4. Simular M con la entrada w, contando los pasos de M.
     Si la cuenta pasa de 2^(2·f(n)), rechazar.
  5. Si M aceptó, rechazar. Si M rechazó, aceptar."

La descripción es de alto nivel, como todas desde la semana 9. Sea A=L(D)A = L(D). Veamos las piezas.

Etapa 2: el límite. Se puede calcular f(n)f(n) dentro de espacio O(f(n))O(f(n)) porque ff es construible. Desde ahí, DD trabaja dentro de las celdas marcadas.

Etapa 3: el relleno. La entrada es la descripción de una máquina, seguida de un 1\mathtt{1} y de cualquier cantidad de ceros: ⟨M⟩10k\langle M \rangle \mathtt{1}\mathtt{0}^k. El 1\mathtt{1} marca dónde termina la descripción, y los ceros solo alargan la entrada. Así cada máquina MM tiene infinitas entradas que “hablan de ella”, de todas las longitudes a partir de cierto punto. Noten que en la etapa 4 se simula a MM con la entrada ww completa, con relleno y todo: lo que importa es que DD y MM respondan distinto con una misma cadena.

Etapa 4: la simulación y el contador. DD tiene un alfabeto de cinta fijo, y MM puede tener cualquiera. Para simular, DD escribe cada símbolo de MM con un bloque de celdas, y guarda aparte el estado de MM y la posición de sus cabezales. Si MM usa g(n)g(n) celdas, DD usa d⋅g(n)d \cdot g(n), donde dd es una constante que depende de MM (de cuántos símbolos y estados tiene) y no de nn. Este es el “poco más” que cuesta simular.

El contador de pasos ocupa 2f(n)+12 f(n) + 1 bits, así que también cabe en espacio O(f(n))O(f(n)). Se guarda en una zona propia de la cinta, fuera de las celdas de la simulación.

Etapa 5: lo contrario. Si la simulación terminó, DD invierte la respuesta.

Esquema de la máquina D en tres franjas. Arriba, la cinta de entrada, de solo lectura, con la cadena w de longitud n: una celda ancha con ⟨M⟩, la máquina que se va a simular; una celda con un 1, que marca el fin de ⟨M⟩; y una fila de ceros, el relleno, que solo alarga la entrada. Al lado, la etapa 3: si w no tiene esta forma, rechazar. En medio, la cinta de trabajo de D. A la izquierda, las f(n) celdas marcadas en la etapa 2: una parte la ocupa la simulación de M con la entrada w, que usa d · g(n) celdas, donde d depende de M y no de n, y el resto queda sin usar. A la derecha, en una zona aparte, el contador de pasos de M, de 2f(n) + 1 bits. Abajo, las tres maneras en que termina la etapa 4, cada una con una flecha desde la pieza que la decide: desde la simulación, M se detuvo y en la etapa 5 se responde lo contrario; desde el borde de las celdas marcadas, la simulación quiere salir de ellas y D rechaza; desde el contador, la cuenta pasa de 2^(2f(n)) y D rechaza. Una nota al pie dice que, si M decide en espacio o(f(n)) y n es grande, d · g(n) es menor que f(n) y M se detiene antes del tope, de modo que la simulación termina y D responde con w lo contrario que M.Esquema de la máquina D en tres franjas. Arriba, la cinta de entrada, de solo lectura, con la cadena w de longitud n: una celda ancha con ⟨M⟩, la máquina que se va a simular; una celda con un 1, que marca el fin de ⟨M⟩; y una fila de ceros, el relleno, que solo alarga la entrada. Al lado, la etapa 3: si w no tiene esta forma, rechazar. En medio, la cinta de trabajo de D. A la izquierda, las f(n) celdas marcadas en la etapa 2: una parte la ocupa la simulación de M con la entrada w, que usa d · g(n) celdas, donde d depende de M y no de n, y el resto queda sin usar. A la derecha, en una zona aparte, el contador de pasos de M, de 2f(n) + 1 bits. Abajo, las tres maneras en que termina la etapa 4, cada una con una flecha desde la pieza que la decide: desde la simulación, M se detuvo y en la etapa 5 se responde lo contrario; desde el borde de las celdas marcadas, la simulación quiere salir de ellas y D rechaza; desde el contador, la cuenta pasa de 2^(2f(n)) y D rechaza. Una nota al pie dice que, si M decide en espacio o(f(n)) y n es grande, d · g(n) es menor que f(n) y M se detiene antes del tope, de modo que la simulación termina y D responde con w lo contrario que M.
Las dos guardas de D: el borde de las celdas marcadas y el tope del contador. Con una máquina de espacio o(f(n)) y una entrada con suficiente relleno no salta ninguna, y D llega a la etapa 5.

Por qué el contador

¿De dónde sale el número 22f(n)2^{2 f(n)}? De contar configuraciones, como en la semana 14. Una configuración de MM es su estado, la posición del cabezal de entrada, la posición del cabezal de trabajo y el contenido de la cinta de trabajo. Si MM usa a lo sumo g(n)g(n) celdas de trabajo, con un alfabeto de cinta Γ\Gamma y un conjunto de estados QQ, la cantidad de configuraciones distintas es a lo sumo

∣Q∣⋅n⋅g(n)⋅∣Γ∣g(n).|Q| \cdot n \cdot g(n) \cdot |\Gamma|^{g(n)}.

Una máquina determinista que se detiene no repite ninguna configuración: si repitiera una, repetiría también todo lo que vino después, para siempre. Entonces, si MM se detiene, lo hace en a lo sumo esa cantidad de pasos.

Ahora supongamos que g(n)=o(f(n))g(n) = o(f(n)). El factor nn es a lo sumo 2f(n)2^{f(n)}, porque f(n)≥log⁡2nf(n) \geq \log_2 n. El resto, ∣Q∣⋅g(n)⋅∣Γ∣g(n)|Q| \cdot g(n) \cdot |\Gamma|^{g(n)}, es a lo sumo 2c⋅g(n)2^{c \cdot g(n)} para alguna constante cc que depende de MM, y c⋅g(n)<f(n)c \cdot g(n) < f(n) cuando nn es grande. En total:

∣Q∣⋅n⋅g(n)⋅∣Γ∣g(n)  ≤  2f(n)⋅2f(n)  =  22f(n)para todo n grande.|Q| \cdot n \cdot g(n) \cdot |\Gamma|^{g(n)} \;\leq\; 2^{f(n)} \cdot 2^{f(n)} \;=\; 2^{2 f(n)} \qquad \text{para todo } n \text{ grande.}

Así que el contador cumple dos funciones a la vez, y hay que comprobar las dos:

  • Corta a las máquinas que no se detienen. Pase lo que pase, la etapa 4 termina en a lo sumo 22f(n)2^{2 f(n)} pasos simulados. DD se detiene con toda entrada.
  • No corta a las máquinas que importan. Una máquina que decide un lenguaje en espacio o(f(n))o(f(n)) se detiene, con las entradas grandes, antes de que el contador llegue al tope.

Error común. Creer que el límite de espacio ya garantiza que la simulación termina. Una máquina puede dar vueltas para siempre dentro de dos celdas. El espacio acotado limita cuántas configuraciones distintas hay, y de ahí sale un límite de tiempo para las máquinas que se detienen. A las que no se detienen hay que cortarlas contando pasos.

La demostración

Demostración del teorema. Por diagonalización. Hay que probar dos cosas: que A=L(D)A = L(D) se decide en espacio O(f(n))O(f(n)), y que ninguna máquina lo decide en espacio o(f(n))o(f(n)).

DD decide AA en espacio O(f(n))O(f(n)). La etapa 2 usa espacio O(f(n))O(f(n)) porque ff es construible. La etapa 3 solo recorre la entrada. La etapa 4 trabaja dentro de las f(n)f(n) celdas marcadas, más el contador, que ocupa 2f(n)+12 f(n) + 1 celdas. Y DD se detiene siempre: las etapas 2 y 3 terminan, y la etapa 4 termina porque el contador tiene un tope. Entonces DD es un decididor y usa espacio O(f(n))O(f(n)).

Ninguna máquina decide AA en espacio o(f(n))o(f(n)). Por contradicción. Supongamos que una máquina MM decide AA usando espacio g(n)g(n), con g(n)=o(f(n))g(n) = o(f(n)). Sea dd la constante con la que DD simula a MM. Como g(n)=o(f(n))g(n) = o(f(n)), existe un n0n_0 tal que para todo n≥n0n \geq n_0 pasan dos cosas:

d⋅g(n)<f(n)yM se detiene en a lo sumo 22f(n) pasos.d \cdot g(n) < f(n) \qquad \text{y} \qquad M \text{ se detiene en a lo sumo } 2^{2 f(n)} \text{ pasos.}

La primera es la definición de oo con la constante 1/d1/d. La segunda es la cuenta de configuraciones de la sección anterior, y usa que MM, por ser un decididor, se detiene.

Tomemos ahora la entrada w=⟨M⟩10n0w = \langle M \rangle \mathtt{1}\mathtt{0}^{n_0}. Su longitud nn es mayor que n0n_0. Sigamos a DD con esa entrada. Pasa la etapa 3, porque ww tiene la forma pedida. En la etapa 4 simula a MM con la entrada ww: la simulación necesita d⋅g(n)<f(n)d \cdot g(n) < f(n) celdas, así que no sale de las marcadas, y MM se detiene antes de que el contador llegue al tope. La simulación termina, entonces, con la respuesta de MM. Y en la etapa 5, DD responde lo contrario:

D acepta w  ⟺  M rechaza w.D \text{ acepta } w \iff M \text{ rechaza } w.

Pero MM decide A=L(D)A = L(D), así que MM acepta ww exactamente cuando DD acepta ww. Las dos cosas no pueden ser ciertas a la vez. La contradicción muestra que tal MM no existe. ∎

Vale la pena comparar con la semana 9, pieza por pieza.

Semana 9: ATMA_{\mathrm{TM}} es indecidible Hoy: jerarquía de espacio
La lista Todas las máquinas de Turing Las máquinas que usan espacio o(f(n))o(f(n))
La casilla de la diagonal MM con la entrada ⟨M⟩\langle M \rangle MM con la entrada ⟨M⟩10k\langle M \rangle \mathtt{1}\mathtt{0}^k, con kk grande
Cómo averigua DD la respuesta Con un decididor HH que se supone que existe Simulando, con un límite de celdas y un contador de pasos
¿DD existe? No: de ahí la contradicción con HH Sí: es una máquina concreta
Qué se concluye Ninguna máquina decide ATMA_{\mathrm{TM}} L(D)L(D) está en una clase y no en la otra

Lo que se agrega es el límite de recursos, y con él tres cosas: la función construible para fijar el límite, el relleno para que la entrada sea lo bastante grande, y el contador para que DD se detenga.

Un número para el relleno

Para ver que el relleno hace falta, pongamos números. Sea f(n)=nf(n) = n, y sea MM una máquina que usa espacio g(n)=100ng(n) = 100 \sqrt{n}, que es o(n)o(n). Supongamos que simularla le cuesta a DD el triple, d=3d = 3. La simulación cabe en las f(n)=nf(n) = n celdas marcadas cuando

300n<n  ⟺  n>300  ⟺  n>90 000.300 \sqrt{n} < n \iff \sqrt{n} > 300 \iff n > 90\,000.

Si la descripción ⟨M⟩\langle M \rangle tiene, digamos, 500 símbolos, con la entrada ⟨M⟩\langle M \rangle la simulación necesitaría 300500≈6708300 \sqrt{500} \approx 6708 celdas y DD solo tiene 500. DD rechaza por falta de espacio, sin saber qué habría respondido MM. Con la entrada ⟨M⟩1090 000\langle M \rangle \mathtt{1}\mathtt{0}^{90\,000}, en cambio, la simulación cabe, y ahí DD y MM quedan enfrentadas. A cada máquina le llega su turno con alguna entrada lo bastante larga, y una sola entrada en la que difieran alcanza.

Lo que el teorema da de inmediato

Corolario. Si f1(n)=o(f2(n))f_1(n) = o(f_2(n)) y f2f_2 es construible en espacio, entonces SPACE(f1(n))⊊SPACE(f2(n))\mathsf{SPACE}(f_1(n)) \subsetneq \mathsf{SPACE}(f_2(n)).

Demostración. La inclusión vale porque f1(n)=O(f2(n))f_1(n) = O(f_2(n)). Es estricta porque el lenguaje AA del teorema, con f=f2f = f_2, está en SPACE(f2(n))\mathsf{SPACE}(f_2(n)) y no se decide en espacio o(f2(n))o(f_2(n)). Toda función que es O(f1(n))O(f_1(n)) es o(f2(n))o(f_2(n)), así que AA no está en SPACE(f1(n))\mathsf{SPACE}(f_1(n)). ∎

En particular:

SPACE(log⁡n)⊊SPACE(log⁡2n)⊊SPACE(n)⊊SPACE(n2)⊊SPACE(n3)⊊⋯\mathsf{SPACE}(\log n) \subsetneq \mathsf{SPACE}(\log^2 n) \subsetneq \mathsf{SPACE}(n) \subsetneq \mathsf{SPACE}(n^2) \subsetneq \mathsf{SPACE}(n^3) \subsetneq \cdots

Dentro de PSPACE hay una escalera infinita, y cada escalón tiene lenguajes que el anterior no tiene.

El teorema de jerarquía de tiempo

Teorema (jerarquía de tiempo). Para toda función tt construible en tiempo existe un lenguaje AA que se decide en tiempo O(t(n))O(t(n)) y que no se decide en tiempo o(t(n)/log⁡t(n))o(t(n) / \log t(n)).

El enunciado es casi el de espacio, con un factor logarítmico de diferencia: aquí no alcanza con “cualquier cantidad que no sea un múltiplo constante”. Hace falta ganarle a la otra máquina por algo más que un factor log⁡t(n)\log t(n). El tiempo se mide como en la semana 12, en máquinas de una cinta.

No haremos la demostración completa. La idea es la de la sección anterior, y lo que interesa es entender de dónde sale el logaritmo.

D = "Con la entrada w:
  1. Sea n la longitud de w.
  2. Calcular t(n) y guardar en un contador binario el número t(n) / log t(n), redondeado hacia arriba.
  3. Si w no tiene la forma ⟨M⟩10* para alguna máquina de Turing M, rechazar.
  4. Simular M con la entrada w. Antes de cada paso propio dedicado a la simulación, restar 1
     al contador. Si el contador llega a 0, rechazar.
  5. Si M aceptó, rechazar. Si M rechazó, aceptar."

Es la misma máquina, con una sola guarda en vez de dos: aquí el contador de pasos es el límite de recursos. Lo nuevo es lo que cuesta llevarlo.

  • En el teorema de espacio, el contador ocupaba celdas, y las celdas se reutilizan: actualizarlo un millón de veces no gasta más espacio que actualizarlo una. Por eso el teorema de espacio no pierde nada.
  • En el teorema de tiempo, cada actualización del contador es tiempo que se va. El contador tiene unos log⁡t(n)\log t(n) bits, y restarle 1 cuesta O(log⁡t(n))O(\log t(n)) pasos. Además, en una máquina de una cinta el contador no puede quedarse en un extremo mientras el cabezal trabaja lejos: ir y volver costaría muchísimo más. La solución es llevarlo consigo, escrito en una pista paralela de la cinta, y moverlo junto con el cabezal simulado. Lo mismo se hace con el estado de MM y su tabla de transiciones.

Con ese cuidado, simular un paso de MM le cuesta a DD una cantidad constante dd de pasos propios, donde dd depende de MM y no de nn, como antes. El contador cuenta esos pasos propios de DD, y cada uno viene acompañado de O(log⁡t(n))O(\log t(n)) pasos más para actualizar el contador. Como el contador empieza en t(n)/log⁡t(n)t(n) / \log t(n), la etapa 4 gasta en total

t(n)log⁡t(n)⋅O(log⁡t(n))=O(t(n)).\frac{t(n)}{\log t(n)} \cdot O(\log t(n)) = O(t(n)).

Así DD corre en tiempo O(t(n))O(t(n)), sea cual sea la máquina que le toque simular. Y si MM termina en g(n)=o(t(n)/log⁡t(n))g(n) = o(t(n) / \log t(n)) pasos, simularla completa pide d⋅g(n)d \cdot g(n) pasos propios, que para nn grande es menos que t(n)/log⁡t(n)t(n) / \log t(n): el contador no la corta. El resto del argumento es el de espacio: el relleno, la entrada larga, la contradicción.

Idea clave. El factor log⁡t(n)\log t(n) es el costo del reloj. En espacio, llevar la cuenta es gratis porque el espacio se reutiliza. En tiempo, mirar el reloj en cada paso cuesta tiempo. El factor sale de cómo se hace la simulación en este modelo, y no de que haga falta tanta ventaja para poder decidir más.

Corolario. Si t1(n)=o(t2(n)/log⁡t2(n))t_1(n) = o(t_2(n) / \log t_2(n)) y t2t_2 es construible en tiempo, entonces TIME(t1(n))⊊TIME(t2(n))\mathsf{TIME}(t_1(n)) \subsetneq \mathsf{TIME}(t_2(n)).

La demostración es la misma del corolario de espacio. Por ejemplo, n2=o(n3/log⁡n3)n^2 = o(n^3 / \log n^3), así que:

TIME(n2)⊊TIME(n3)⊊TIME(n4)⊊⋯\mathsf{TIME}(n^2) \subsetneq \mathsf{TIME}(n^3) \subsetneq \mathsf{TIME}(n^4) \subsetneq \cdots

También dentro de P hay una escalera infinita. Para cada k≥1k \geq 1 existe un lenguaje que se decide en tiempo O(nk+1)O(n^{k+1}) y no en tiempo O(nk)O(n^k).

Error común. Leer el teorema de jerarquía como “con más tiempo todo problema se resuelve mejor”. El teorema dice que existe algún lenguaje al que más tiempo le sirve: el lenguaje AA, construido a propósito con la diagonal. No dice nada de un problema que a ustedes les interese. El lenguaje { 0k1k:k≥0 }\{\, \mathtt{0}^k\mathtt{1}^k : k \geq 0 \,\} se decide en tiempo O(nlog⁡n)O(n \log n), y darle tiempo n5n^5 no cambia nada. Y que SAT se pueda decidir en tiempo 2n2^n no implica que necesite tanto: para saber eso habría que resolver P frente a NP. Los teoremas de jerarquía separan clases. Decir cuánto cuesta un problema concreto es otra tarea, casi siempre más difícil.

Lo que se sabe distinto: las consecuencias

Con los dos teoremas y el teorema de Savitch de la semana 14 salen todas las separaciones conocidas de la cadena.

Teorema. P≠EXPTIME\mathsf{P} \neq \mathsf{EXPTIME}.

Demostración. La función 2n2^n es construible en tiempo. Por el teorema de jerarquía de tiempo existe un lenguaje AA que se decide en tiempo O(2n)O(2^n) y no se decide en tiempo o(2n/log⁡2n)=o(2n/n)o(2^n / \log 2^n) = o(2^n / n).

AA está en EXPTIME, porque TIME(2n)⊆EXPTIME\mathsf{TIME}(2^n) \subseteq \mathsf{EXPTIME}.

AA no está en P. Si estuviera, se decidiría en tiempo O(nk)O(n^k) para algún kk. Pero nk=o(2n/n)n^k = o(2^n / n) para todo kk, porque una exponencial crece más rápido que cualquier polinomio. Entonces AA se decidiría en tiempo o(2n/n)o(2^n / n), y eso contradice lo que sabemos de AA. ∎

Teorema. NL≠PSPACE\mathsf{NL} \neq \mathsf{PSPACE}, y por lo tanto L≠PSPACE\mathsf{L} \neq \mathsf{PSPACE}.

Demostración. Son tres pasos:

NL=NSPACE(log⁡n)  ⊆  SPACE(log⁡2n)  ⊊  SPACE(n)  ⊆  PSPACE.\mathsf{NL} = \mathsf{NSPACE}(\log n) \;\subseteq\; \mathsf{SPACE}(\log^2 n) \;\subsetneq\; \mathsf{SPACE}(n) \;\subseteq\; \mathsf{PSPACE}.

El primero es el teorema de Savitch, NSPACE(f(n))⊆SPACE(f(n)2)\mathsf{NSPACE}(f(n)) \subseteq \mathsf{SPACE}(f(n)^2), con f(n)=log⁡nf(n) = \log n: el teorema vale también para cotas menores que nn, desde log⁡n\log n, con la cinta de entrada de solo lectura. El segundo es el corolario de la jerarquía de espacio: log⁡2n=o(n)\log^2 n = o(n), y nn es construible en espacio. El tercero es la definición de PSPACE. Como en medio hay una inclusión estricta, NL no es todo PSPACE.

Para L: como L⊆NL\mathsf{L} \subseteq \mathsf{NL}, si L fuera igual a PSPACE también lo sería NL. ∎

Aquí Savitch es indispensable. El teorema de jerarquía solo compara clases deterministas entre sí. Para decir algo de NL, que es no determinista, primero hay que meterla en una clase determinista, y eso es lo que hace Savitch.

La cadena, par por par

En la cadena hay seis clases y, por lo tanto, 15 pares. Esto es todo lo que se sabe.

NL P NP PSPACE EXPTIME
L ? ? ? ≠\neq ≠\neq
NL ? ? ≠\neq ≠\neq
P ? ? ≠\neq
NP ? ?
PSPACE ?

Cinco pares son distintos con seguridad:

  • NL≠PSPACE\mathsf{NL} \neq \mathsf{PSPACE} y L≠PSPACE\mathsf{L} \neq \mathsf{PSPACE}, por el teorema de arriba.
  • P≠EXPTIME\mathsf{P} \neq \mathsf{EXPTIME}, por el teorema de arriba.
  • NL≠EXPTIME\mathsf{NL} \neq \mathsf{EXPTIME} y L≠EXPTIME\mathsf{L} \neq \mathsf{EXPTIME}, porque L⊆NL⊆P\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{P} y P ya es distinta de EXPTIME.

De los otros diez no se sabe nada, y ahí están todas las preguntas famosas: L frente a NL, P frente a NP, NP frente a PSPACE. Tampoco se sabe si NP es distinta de EXPTIME.

La cadena de seis clases en una fila: L, NL, P, NP, PSPACE y EXPTIME, con el signo de inclusión entre cada clase y la siguiente y un signo de interrogación encima de cada uno, porque de ninguna de las cinco inclusiones se sabe si es estricta. Cinco arcos unen los pares que se sabe que son distintos. Dos son gruesos, los de los teoremas: de P a EXPTIME, rotulado jerarquía de tiempo, y de NL a PSPACE, rotulado Savitch y jerarquía de espacio. Tres son delgados, los que se siguen de los otros: de NL a EXPTIME, porque NL está contenida en P; de L a EXPTIME, porque L está contenida en P; y de L a PSPACE, porque L está contenida en NL. Una leyenda explica los dos tipos de arco y el signo de inclusión con interrogación. Al pie: de los otros diez pares no se sabe nada, y entre P y EXPTIME al menos una de las tres inclusiones es estricta.La cadena de seis clases en una fila: L, NL, P, NP, PSPACE y EXPTIME, con el signo de inclusión entre cada clase y la siguiente y un signo de interrogación encima de cada uno, porque de ninguna de las cinco inclusiones se sabe si es estricta. Cinco arcos unen los pares que se sabe que son distintos. Dos son gruesos, los de los teoremas: de P a EXPTIME, rotulado jerarquía de tiempo, y de NL a PSPACE, rotulado Savitch y jerarquía de espacio. Tres son delgados, los que se siguen de los otros: de NL a EXPTIME, porque NL está contenida en P; de L a EXPTIME, porque L está contenida en P; y de L a PSPACE, porque L está contenida en NL. Una leyenda explica los dos tipos de arco y el signo de inclusión con interrogación. Al pie: de los otros diez pares no se sabe nada, y entre P y EXPTIME al menos una de las tres inclusiones es estricta.
La tabla de pares sobre la cadena. Todos los arcos saltan al menos dos eslabones: no se conoce ninguna separación entre dos clases vecinas.

Aun así, las separaciones conocidas dicen algo sobre las desconocidas:

  • En P⊆NP⊆PSPACE⊆EXPTIME\mathsf{P} \subseteq \mathsf{NP} \subseteq \mathsf{PSPACE} \subseteq \mathsf{EXPTIME}, los extremos son distintos. Entonces al menos una de las tres inclusiones es estricta. No se sabe cuál. Se cree que las tres.
  • En NL⊆P⊆NP⊆PSPACE\mathsf{NL} \subseteq \mathsf{P} \subseteq \mathsf{NP} \subseteq \mathsf{PSPACE} pasa lo mismo: al menos una es estricta.

Es una situación curiosa. Hay un teorema que dice “alguna de estas tres afirmaciones es verdadera”, y para ninguna de las tres hay una demostración.

Un problema que no está en P, por teorema

Hasta hoy, cada vez que dijimos que un problema “no tiene algoritmo polinomial” fue con un “se cree”: los problemas NP-completos no están en P si P≠NP\mathsf{P} \neq \mathsf{NP}. Con el teorema de jerarquía hay problemas que no están en P sin ningún “si”.

El primero es el lenguaje AA de la demostración, que es artificial. Uno más natural es la versión con reloj del problema de aceptación:

ATMreloj={ ⟨M,w,k⟩:M acepta w en a lo sumo k pasos },A_{\mathrm{TM}}^{\mathrm{reloj}} = \{\, \langle M, w, k \rangle : M \text{ acepta } w \text{ en a lo sumo } k \text{ pasos} \,\},

donde MM es una máquina de Turing determinista y kk está escrito en binario.

Afirmación. ATMrelojA_{\mathrm{TM}}^{\mathrm{reloj}} es decidible y no está en P.

Demostración. Es decidible: se simula a MM con ww durante kk pasos. Como la simulación tiene un tope, siempre termina. Cuesta un tiempo polinomial en kk y en el tamaño de ⟨M,w⟩\langle M, w \rangle. Pero kk está en binario: si la entrada tiene longitud nn, kk puede valer hasta 2n2^n. El algoritmo corre en tiempo 2O(n)2^{O(n)}, así que el lenguaje está en EXPTIME.

No está en P, por reducción. Mostramos que todo lenguaje de EXPTIME se reduce en tiempo polinomial a ATMrelojA_{\mathrm{TM}}^{\mathrm{reloj}}. La dirección es esa porque queremos concluir que ATMrelojA_{\mathrm{TM}}^{\mathrm{reloj}} es al menos tan difícil como cualquier lenguaje de EXPTIME. Sea BB un lenguaje de EXPTIME, y sea MBM_B una máquina que lo decide en a lo sumo 2nc+c2^{n^c + c} pasos, para alguna constante cc. La reducción es

f(w)=⟨MB,  w,  2∣w∣c+c⟩.f(w) = \langle M_B,\; w,\; 2^{|w|^c + c} \rangle.

Se calcula en tiempo polinomial: MBM_B es fija, y el número 2∣w∣c+c2^{|w|^c + c} en binario es un 1\mathtt{1} seguido de ∣w∣c+c|w|^c + c ceros. Y w∈Bw \in B si y solo si MBM_B acepta ww dentro de su tiempo, es decir, si y solo si f(w)∈ATMrelojf(w) \in A_{\mathrm{TM}}^{\mathrm{reloj}}.

Si ATMrelojA_{\mathrm{TM}}^{\mathrm{reloj}} estuviera en P, todo lenguaje BB de EXPTIME estaría en P: se calcula f(w)f(w) y se decide. Tendríamos EXPTIME⊆P\mathsf{EXPTIME} \subseteq \mathsf{P}, contra el teorema P≠EXPTIME\mathsf{P} \neq \mathsf{EXPTIME}. ∎

El detalle del binario es el mismo de la semana 12. Con kk en unario, el mismo problema está en P: simular kk pasos es polinomial en la longitud de la entrada, que ya incluye kk símbolos.

La demostración muestra algo más: ATMrelojA_{\mathrm{TM}}^{\mathrm{reloj}} es EXPTIME-completo, en el mismo sentido en que SAT es NP-completo. Hay otros problemas EXPTIME-completos que no hablan de máquinas. Los más conocidos son juegos: decidir quién gana desde una posición dada del ajedrez o de las damas, generalizados a un tablero de n×nn \times n, es EXPTIME-completo. No lo demostraremos. La consecuencia sí cabe en una línea: ninguno de esos problemas tiene un algoritmo polinomial, y eso es un teorema, sin conjetura de por medio.

En la práctica. Para un tablero de tamaño fijo, como el de 8×88 \times 8, todo esto no dice nada: hay una cantidad finita de posiciones, y un problema con una cantidad finita de entradas se decide en tiempo constante, con una tabla. La complejidad habla de cómo crece el costo con el tamaño. Que un programa juegue bien al ajedrez de verdad es un asunto de ingeniería, no de clases de complejidad.

Oráculos y los límites de la diagonalización

Sección opcional (✂️).

La diagonalización separó P de EXPTIME. La pregunta natural es por qué no separa P de NP. No es por falta de intentos, y hay un resultado que explica qué es lo que falla. Para enunciarlo hace falta un tipo nuevo de máquina.

Máquinas con oráculo

Un oráculo (oracle) para un lenguaje AA es un dispositivo que responde, en un solo paso, si una cadena está en AA. Una máquina de Turing con oráculo MAM^A es una máquina de Turing con una cinta adicional, la cinta de consulta. Cuando la máquina escribe una cadena qq en esa cinta y entra en un estado especial, en el paso siguiente recibe la respuesta: sí, si q∈Aq \in A; no, si q∉Aq \notin A. Escribir la consulta cuesta lo que cuesta escribirla. La respuesta es gratis, sea AA fácil, difícil o indecidible.

En términos de programación, es un programa que puede llamar a una función en_A(q) que alguien más implementó, y cuyo costo no se le cobra.

Con eso se definen las clases relativas a AA:

  • PA\mathsf{P}^A: los lenguajes que decide una máquina determinista de tiempo polinomial con oráculo AA.
  • NPA\mathsf{NP}^A: lo mismo con una máquina no determinista.

Siempre vale PA⊆NPA\mathsf{P}^A \subseteq \mathsf{NP}^A, por la razón de siempre. Con un oráculo trivial, como A=∅A = \emptyset, se recuperan P y NP.

Dos oráculos que responden distinto

Teorema. Existe un oráculo AA con PA=NPA\mathsf{P}^A = \mathsf{NP}^A, y existe un oráculo BB con PB≠NPB\mathsf{P}^B \neq \mathsf{NP}^B.

El oráculo AA. Sea A=TQBFA = \mathrm{TQBF}, el problema PSPACE-completo de la semana 14. Entonces:

NPTQBF  ⊆  NPSPACE  =  PSPACE  ⊆  PTQBF.\mathsf{NP}^{\mathrm{TQBF}} \;\subseteq\; \mathsf{NPSPACE} \;=\; \mathsf{PSPACE} \;\subseteq\; \mathsf{P}^{\mathrm{TQBF}}.

La primera inclusión: una máquina no determinista de tiempo polinomial con oráculo TQBF se simula sin oráculo en espacio polinomial, calculando la respuesta de cada consulta con el algoritmo de espacio polinomial para TQBF. Las consultas tienen longitud polinomial, porque la máquina tuvo que escribirlas. La igualdad es Savitch. La última inclusión: como TQBF es PSPACE-completo, todo lenguaje de PSPACE se decide reduciéndolo a TQBF en tiempo polinomial y haciendo una sola consulta. Junto con PA⊆NPA\mathsf{P}^A \subseteq \mathsf{NP}^A, las dos clases son iguales.

La intuición: el oráculo es tan poderoso que hace por su cuenta todo lo que el no determinismo podría agregar.

El oráculo BB, la idea. Para cualquier lenguaje BB, consideren

LB={ 1n:B contiene alguna cadena de longitud n }.L_B = \{\, \mathtt{1}^n : B \text{ contiene alguna cadena de longitud } n \,\}.

LBL_B está en NPB\mathsf{NP}^B sea cual sea BB: la máquina adivina una cadena de longitud nn y le pregunta al oráculo si está. Una máquina determinista, en cambio, tendría que buscar entre 2n2^n cadenas, y en tiempo polinomial solo puede preguntar por una cantidad polinomial. Hay que construir BB de modo que ninguna búsqueda corta funcione.

Se construye por etapas, con una diagonal. Se listan las máquinas deterministas con oráculo de tiempo polinomial, M1,M2,…M_1, M_2, \ldots, de modo que MiM_i dé a lo sumo nin^i pasos. Se puede: a cada máquina se le agrega un reloj, y cada una aparece en la lista infinitas veces, con relojes cada vez mayores. En la etapa ii se elige un nn mayor que todas las longitudes tocadas en las etapas anteriores, y tal que ni<2nn^i < 2^n. Se corre MiM_i con la entrada 1n\mathtt{1}^n. Cuando pregunta por una cadena cuyo destino ya está decidido, se le responde eso; cuando pregunta por una nueva, se le responde que no, y esa cadena queda fuera de BB para siempre. Como MiM_i hace menos de 2n2^n consultas, queda alguna cadena de longitud nn por la que no preguntó. Ahora se mira la respuesta de MiM_i:

  • Si aceptó 1n\mathtt{1}^n, ninguna cadena de longitud nn entra en BB. Entonces 1n∉LB\mathtt{1}^n \notin L_B, y MiM_i se equivocó.
  • Si rechazó, se pone en BB una cadena de longitud nn por la que no preguntó. Entonces 1n∈LB\mathtt{1}^n \in L_B, y MiM_i se equivocó. Su ejecución no cambia, porque nunca consultó esa cadena.

Al final, cada MiM_i falla con alguna entrada. LBL_B no está en PB\mathsf{P}^B y sí en NPB\mathsf{NP}^B.

Qué significa: la relativización

Miren otra vez la demostración del teorema de jerarquía. La máquina DD trata a MM como una caja: la simula paso a paso y mira la respuesta. Si les damos a todas las máquinas el mismo oráculo AA, la demostración sigue funcionando sin cambiar una palabra: cuando MAM^A hace una consulta, DAD^A hace la misma consulta a su propio oráculo y le pasa la respuesta. Lo mismo pasa con las simulaciones que dieron P⊆NP⊆EXPTIME\mathsf{P} \subseteq \mathsf{NP} \subseteq \mathsf{EXPTIME}.

Se dice que una demostración así relativiza (relativization): vale igual en un mundo donde todas las máquinas tienen acceso al mismo oráculo, cualquiera que sea.

Ahora el argumento, que es corto.

  • Si una demostración que relativiza probara que P≠NP\mathsf{P} \neq \mathsf{NP}, probaría también que PA≠NPA\mathsf{P}^A \neq \mathsf{NP}^A para todo oráculo AA. Eso es falso para A=TQBFA = \mathrm{TQBF}.
  • Si una demostración que relativiza probara que P=NP\mathsf{P} = \mathsf{NP}, probaría también que PB=NPB\mathsf{P}^B = \mathsf{NP}^B para todo oráculo BB. Eso es falso para el BB de arriba.

Conclusión. Ninguna demostración que relativice puede resolver P frente a NP, en ninguno de los dos sentidos. En particular, no alcanza con simular y diagonalizar tratando a las máquinas como cajas.

Hay que leer esto con cuidado, porque se exagera con facilidad.

  • No dice que P frente a NP no se pueda resolver. Dice qué tipo de demostración no sirve.
  • No dice que la diagonalización sea inútil en complejidad: acabamos de usarla. Dice que, para esta pregunta, hace falta además algún ingrediente que mire dentro del cómputo, que use cómo funciona un paso de una máquina y no solo lo que responde.
  • Esos ingredientes existen. La demostración de Cook-Levin mira dentro: describe cada paso con ventanas del tableau. Y el teorema IP=PSPACE\mathsf{IP} = \mathsf{PSPACE}, que aparece más abajo, es un resultado que no relativiza. Para P frente a NP, hasta hoy, ninguna técnica conocida alcanza.

Máquinas que lanzan monedas

Hasta aquí una máquina tenía dos maneras de avanzar. La determinista da un paso fijo. La no determinista tiene varias opciones y acepta si alguna rama acepta; es una definición, y ninguna computadora funciona así. Ahora viene una tercera, que sí se puede construir: la máquina que, cuando tiene dos opciones, lanza una moneda.

Una máquina de Turing probabilística es una máquina de Turing no determinista en la que cada paso tiene una o dos opciones. Cuando hay dos, se elige una con una moneda justa: probabilidad 1/21/2 cada una, y cada lanzamiento es independiente de los anteriores. Una rama de la ejecución en la que se lanzaron mm monedas tiene probabilidad 2−m2^{-m}. La probabilidad de que la máquina acepte ww es la suma de las probabilidades de las ramas que aceptan.

Es el mismo árbol de ejecuciones de la semana 2 y de la semana 12, y lo que cambia es la pregunta que se le hace:

Máquina Acepta ww si…
No determinista alguna rama acepta
Probabilística la mayor parte de las ramas acepta, medida por su probabilidad

Hay otra manera de decir lo mismo, que es la que se programa. Un algoritmo probabilístico es un algoritmo determinista M(w,r)M(w, r) que recibe, además de la entrada ww, una cadena rr de bits al azar. Compárenlo con el verificador de la semana 12, que recibía ww y un certificado cc: en NP se pregunta si existe una cadena cc que haga aceptar; aquí se pregunta qué fracción de las cadenas rr hace aceptar.

De probabilidad solo usaremos lo elemental:

  • Si un experimento tiene NN resultados igualmente probables y un evento ocurre en KK de ellos, su probabilidad es K/NK/N.
  • Si dos eventos son independientes, la probabilidad de que ocurran los dos es el producto de sus probabilidades. Dos ejecuciones de un algoritmo con monedas distintas son independientes.

No hace falta más. En particular, no usaremos esperanzas ni varianzas.

Error común. Confundir el azar del algoritmo con el azar de la entrada. Aquí la entrada no es al azar: es la que sea, también la peor. Lo único aleatorio son las monedas del algoritmo. Cuando digamos “se equivoca con probabilidad a lo sumo 1/21/2”, será para toda entrada, y la probabilidad se calcula sobre las monedas. No hay entradas “con mala suerte” en las que el algoritmo falle siempre.

Verificar un producto sin multiplicar

El problema: dadas tres matrices AA, BB y CC de n×nn \times n, ¿es cierto que A⋅B=CA \cdot B = C?

La manera obvia es calcular A⋅BA \cdot B y comparar. Con la definición del producto son n3n^3 multiplicaciones. Los mejores algoritmos conocidos para multiplicar matrices bajan el exponente hasta un poco menos de 2,382{,}38, pero son tan complicados que no se usan, y nadie sabe multiplicar en tiempo O(n2)O(n^2). Leer las tres matrices ya cuesta n2n^2, así que O(n2)O(n^2) es lo mejor que se puede esperar. ¿Se puede comprobar un producto más rápido de lo que se sabe calcularlo?

El algoritmo de Freivalds

La idea es no comparar las matrices, sino lo que le hacen a un vector. Si A⋅B=CA \cdot B = C, entonces para cualquier vector rr vale A⋅(B⋅r)=C⋅rA \cdot (B \cdot r) = C \cdot r. Y multiplicar una matriz por un vector cuesta solo n2n^2.

algoritmo freivalds(A, B, C)
    r ← un vector de n bits, cada uno 0 o 1 con una moneda independiente
    x ← B · r
    y ← A · x
    z ← C · r
    si y = z entonces
        devolver "iguales"
    sino
        devolver "distintos"
    fin si
fin algoritmo

Son tres productos de matriz por vector: 3n23n^2 multiplicaciones. La clave está en el orden: se calcula primero B⋅rB \cdot r, que es un vector, y después AA por ese vector. Nunca se calcula A⋅BA \cdot B.

¿Qué puede salir mal?

  • Si A⋅B=CA \cdot B = C, entonces y=zy = z para todo rr. El algoritmo responde “iguales” siempre. Aquí no se equivoca nunca.
  • Si A⋅B≠CA \cdot B \neq C, puede pasar que justo el vector rr elegido no note la diferencia y dé y=zy = z. Entonces responde “iguales”, y se equivoca.

El error solo es posible de un lado. Cuando el algoritmo responde “distintos” tiene una prueba en la mano: un vector rr con A⋅(B⋅r)≠C⋅rA \cdot (B \cdot r) \neq C \cdot r. Esa respuesta es segura.

Un ejemplo, con todos los vectores

Con n=3n = 3 hay solo 23=82^3 = 8 vectores, y se pueden probar todos. El programa freivalds_demo toma dos matrices pequeñas y tres matrices CC incorrectas.

$ build/freivalds_demo
A   =   1   2   0
        0   1   3
        2   0   1
B   =   2   1   0
        1   0   2
        0   3   1
A·B =   4   1   4
        1   9   5
        4   5   1

C1: igual a A·B salvo la entrada (2, 3), que vale 6 en vez de 5.
  r           B·r            A·(B·r)         C·r             ¿detecta?
  (0, 0, 0)   (0, 0, 0)      (0, 0, 0)       (0, 0, 0)       no
  (0, 0, 1)   (0, 2, 1)      (4, 5, 1)       (4, 6, 1)       sí
  (0, 1, 0)   (1, 0, 3)      (1, 9, 5)       (1, 9, 5)       no
  (0, 1, 1)   (1, 2, 4)      (5, 14, 6)      (5, 15, 6)      sí
  (1, 0, 0)   (2, 1, 0)      (4, 1, 4)       (4, 1, 4)       no
  (1, 0, 1)   (2, 3, 1)      (8, 6, 5)       (8, 7, 5)       sí
  (1, 1, 0)   (3, 1, 3)      (5, 10, 9)      (5, 10, 9)      no
  (1, 1, 1)   (3, 3, 4)      (9, 15, 10)     (9, 16, 10)     sí
  Detectan la diferencia 4 de 8 vectores.

Sigan una fila a mano. Con r=(0,1,1)r = (0, 1, 1), el vector B⋅rB \cdot r es la suma de la segunda y la tercera columna de BB: (1+0,  0+2,  3+1)=(1,2,4)(1 + 0,\; 0 + 2,\; 3 + 1) = (1, 2, 4). Después A⋅(1,2,4)=(1+4,  2+12,  2+4)=(5,14,6)A \cdot (1, 2, 4) = (1 + 4,\; 2 + 12,\; 2 + 4) = (5, 14, 6). Y C1⋅rC_1 \cdot r es la suma de la segunda y la tercera columna de C1C_1: (1+4,  9+6,  5+1)=(5,15,6)(1 + 4,\; 9 + 6,\; 5 + 1) = (5, 15, 6). Difieren en la segunda coordenada, y la diferencia queda detectada.

Animación de dos rondas del algoritmo de Freivalds con las matrices A, B y C1 del ejemplo; en C1 está marcada la entrada (2, 3), que vale 6 en vez de 5. A la izquierda se calculan x = B·r y después y = A·x; a la derecha, z = C1·r y la comparación de y con z. Ronda 1. Paso 1: tres monedas dan r = (1, 1, 0). Paso 2: se resaltan las columnas 1 y 2 de B, y su suma es x = (3, 1, 3). Paso 3: y = A·x = (5, 10, 9). Paso 4: se resaltan las columnas 1 y 2 de C1, y su suma es z = (5, 10, 9); la columna 3, donde está la entrada distinta, no entró. Paso 5: y y z coinciden en las tres coordenadas, y la ronda responde iguales, que es un error. Ronda 2. Paso 6: tres monedas nuevas dan r = (0, 1, 1). Paso 7: se resaltan las columnas 2 y 3 de B, y x = (1, 2, 4). Paso 8: y = A·x = (5, 14, 6). Paso 9: se resaltan las columnas 2 y 3 de C1, y z = (5, 15, 6). Paso 10: y y z difieren en la segunda coordenada, 14 contra 15; la ronda responde distintos, que es una respuesta segura, y el algoritmo termina.Animación de dos rondas del algoritmo de Freivalds con las matrices A, B y C1 del ejemplo; en C1 está marcada la entrada (2, 3), que vale 6 en vez de 5. A la izquierda se calculan x = B·r y después y = A·x; a la derecha, z = C1·r y la comparación de y con z. Ronda 1. Paso 1: tres monedas dan r = (1, 1, 0). Paso 2: se resaltan las columnas 1 y 2 de B, y su suma es x = (3, 1, 3). Paso 3: y = A·x = (5, 10, 9). Paso 4: se resaltan las columnas 1 y 2 de C1, y su suma es z = (5, 10, 9); la columna 3, donde está la entrada distinta, no entró. Paso 5: y y z coinciden en las tres coordenadas, y la ronda responde iguales, que es un error. Ronda 2. Paso 6: tres monedas nuevas dan r = (0, 1, 1). Paso 7: se resaltan las columnas 2 y 3 de B, y x = (1, 2, 4). Paso 8: y = A·x = (5, 14, 6). Paso 9: se resaltan las columnas 2 y 3 de C1, y z = (5, 15, 6). Paso 10: y y z difieren en la segunda coordenada, 14 contra 15; la ronda responde distintos, que es una respuesta segura, y el algoritmo termina.
Dos filas de la tabla, hechas paso a paso. Con r = (1, 1, 0) la columna del error no entra en la suma y la ronda se equivoca; con r = (0, 1, 1) sí entra. En ningún momento se calcula A·B.

Miren ahora qué vectores detectan: exactamente los que tienen un 1 en la tercera coordenada. Tiene sentido. Multiplicar una matriz por un vector de ceros y unos es sumar las columnas elegidas. La única entrada mala de C1C_1 está en la tercera columna, y se nota si y solo si esa columna entra en la suma. Eso pasa con la mitad de los vectores.

El programa sigue con otras dos matrices. Aquí va solo la línea final de cada una:

C2: en la fila 1, la entrada (1, 1) vale uno más y la (1, 2) uno menos.
  Detectan la diferencia 4 de 8 vectores.

C3: las tres entradas de la diagonal valen uno más.
  Detectan la diferencia 7 de 8 vectores.

C2C_2 tiene dos errores en la misma fila, uno de +1+1 y otro de −1-1. Si las dos columnas entran en la suma, o ninguna, los errores se cancelan o no aparecen: detectan los vectores con r1≠r2r_1 \neq r_2, que otra vez son la mitad. En particular, el vector de solo unos (1,1,1)(1, 1, 1) no detecta nada: comparar la suma de cada fila no es una prueba confiable. C3C_3 tiene un error en cada columna, y solo el vector nulo deja de verlo.

En los tres casos detecta al menos la mitad de los vectores. No es casualidad.

Por qué al menos la mitad

Teorema. Sean AA, BB y CC matrices de n×nn \times n con entradas enteras. Si A⋅B≠CA \cdot B \neq C, de los 2n2^n vectores rr de ceros y unos, al menos la mitad cumple A⋅(B⋅r)≠C⋅rA \cdot (B \cdot r) \neq C \cdot r. Por lo tanto, el algoritmo de Freivalds se equivoca con probabilidad a lo sumo 1/21/2.

Demostración. Por conteo: emparejamos los vectores de dos en dos y mostramos que en cada pareja al menos uno detecta la diferencia.

Sea D=A⋅B−CD = A \cdot B - C. Como el producto de matrices es asociativo y distributivo,

A⋅(B⋅r)−C⋅r=(A⋅B−C)⋅r=D⋅r.A \cdot (B \cdot r) - C \cdot r = (A \cdot B - C) \cdot r = D \cdot r.

Entonces el vector rr detecta la diferencia exactamente cuando D⋅r≠0D \cdot r \neq 0. La matriz DD no es nula, porque A⋅B≠CA \cdot B \neq C. Sea dijd_{ij} una entrada no nula de DD, en la fila ii y la columna jj. Vamos a mirar solo la coordenada ii de D⋅rD \cdot r:

(D⋅r)i=∑l=1ndil rl=dij rj+s,donde s=∑l≠jdil rl.(D \cdot r)_i = \sum_{l=1}^{n} d_{il}\, r_l = d_{ij}\, r_j + s, \qquad \text{donde } s = \sum_{l \neq j} d_{il}\, r_l.

El número ss depende de todas las coordenadas de rr menos la jj.

Ahora las parejas. Emparejamos cada vector con el que se obtiene cambiándole solo la coordenada jj. Los 2n2^n vectores quedan repartidos en 2n−12^{n-1} parejas, y los dos vectores de una pareja tienen el mismo ss. Para el que tiene rj=0r_j = 0, la coordenada ii de D⋅rD \cdot r vale ss. Para el que tiene rj=1r_j = 1, vale s+dijs + d_{ij}. Como dij≠0d_{ij} \neq 0, esos dos números son distintos, así que no pueden ser cero los dos. Al menos uno de los dos vectores de la pareja tiene (D⋅r)i≠0(D \cdot r)_i \neq 0 y, por lo tanto, D⋅r≠0D \cdot r \neq 0.

Hay 2n−12^{n-1} parejas y cada una aporta al menos un vector que detecta la diferencia. Son al menos 2n−12^{n-1} de 2n2^n: la mitad. El algoritmo elige rr con nn monedas independientes, así que los 2n2^n vectores son igualmente probables, y la probabilidad de elegir uno que no detecta es a lo sumo 1/21/2. ∎

La demostración no supone nada sobre AA, BB y CC, salvo que A⋅B≠CA \cdot B \neq C. No hay matrices “difíciles” para Freivalds: la cota vale para todas.

En el ejemplo, con C1C_1, la entrada no nula de DD es d23=−1d_{23} = -1. Las parejas son los vectores que solo difieren en la tercera coordenada: (0,0,0)(0,0,0) con (0,0,1)(0,0,1), (0,1,0)(0,1,0) con (0,1,1)(0,1,1), y así. En la tabla, de cada pareja detecta exactamente uno. Cuando DD tiene una sola entrada no nula, la cota se alcanza: la probabilidad de fallar es exactamente 1/21/2. Es el peor caso, y es el que usaremos en los experimentos.

Dos paneles con los ocho vectores de ceros y unos, emparejados. En cada pareja, una línea une dos vectores, y junto a cada vector está el valor de la coordenada de D·r que se mira; los vectores que detectan la diferencia están resaltados. Panel izquierdo, C1, con una sola entrada distinta, d_23 = −1: las parejas solo difieren en r_3 y se mira la coordenada 2. Son (0,0,0) con (0,0,1), (0,1,0) con (0,1,1), (1,0,0) con (1,0,1) y (1,1,0) con (1,1,1). En las cuatro, el vector con r_3 = 0 da 0 y no detecta, y el vector con r_3 = 1 da −1 y detecta. Aquí s vale 0 siempre y de cada pareja detecta exactamente uno: es el peor caso. Panel derecho, C2, con d_11 = −1 y d_12 = +1: las parejas solo difieren en r_1 y se mira la coordenada 1. En (0,0,0) con (1,0,0) y en (0,0,1) con (1,0,1) los valores son 0 y −1, y detecta el segundo. En (0,1,0) con (1,1,0) y en (0,1,1) con (1,1,1) los valores son 1 y 0, y detecta el primero. Aquí s es igual a r_2. Al pie: en una pareja, la coordenada i de D·r vale s y s + d_ij; como d_ij no es cero, no pueden ser cero los dos.Dos paneles con los ocho vectores de ceros y unos, emparejados. En cada pareja, una línea une dos vectores, y junto a cada vector está el valor de la coordenada de D·r que se mira; los vectores que detectan la diferencia están resaltados. Panel izquierdo, C1, con una sola entrada distinta, d_23 = −1: las parejas solo difieren en r_3 y se mira la coordenada 2. Son (0,0,0) con (0,0,1), (0,1,0) con (0,1,1), (1,0,0) con (1,0,1) y (1,1,0) con (1,1,1). En las cuatro, el vector con r_3 = 0 da 0 y no detecta, y el vector con r_3 = 1 da −1 y detecta. Aquí s vale 0 siempre y de cada pareja detecta exactamente uno: es el peor caso. Panel derecho, C2, con d_11 = −1 y d_12 = +1: las parejas solo difieren en r_1 y se mira la coordenada 1. En (0,0,0) con (1,0,0) y en (0,0,1) con (1,0,1) los valores son 0 y −1, y detecta el segundo. En (0,1,0) con (1,1,0) y en (0,1,1) con (1,1,1) los valores son 1 y 0, y detecta el primero. Aquí s es igual a r_2. Al pie: en una pareja, la coordenada i de D·r vale s y s + d_ij; como d_ij no es cero, no pueden ser cero los dos.
Los dos valores de una pareja difieren en una cantidad que no es cero, así que a lo sumo uno de los dos vectores deja de ver la diferencia. Con C2 la pareja se arma con la entrada (1, 1), y el que detecta cambia de lado según s.

Módulo un primo

Con enteros de verdad hay un problema práctico. Si las entradas de AA y de BB llegan a 10910^9 y n=2000n = 2000, una entrada de A⋅(B⋅r)A \cdot (B \cdot r) puede llegar a 2000⋅109⋅2000⋅109=4⋅10242000 \cdot 10^9 \cdot 2000 \cdot 10^9 = 4 \cdot 10^{24}, que no cabe en 64 bits. La salida usual es hacer todas las cuentas módulo un primo pp: se trabaja con los restos, que siempre son menores que pp.

El código de la semana usa p=109+7=1 000 000 007p = 10^9 + 7 = 1\,000\,000\,007, un primo menor que 2302^{30}. Las matrices tienen entradas en {0,1,…,p−1}\{0, 1, \ldots, p - 1\}, y la pregunta pasa a ser si A⋅B=CA \cdot B = C módulo pp: si cada entrada de A⋅BA \cdot B deja el mismo resto que la de CC.

El teorema sigue valiendo, con la misma demostración. Ahora D=A⋅B−CD = A \cdot B - C tiene alguna entrada dijd_{ij} que no es múltiplo de pp. En una pareja, las coordenadas ii valen ss y s+dijs + d_{ij}; si las dos fueran múltiplos de pp, su diferencia dijd_{ij} también lo sería. Así que a lo sumo una de las dos es cero módulo pp, y al menos la mitad de los vectores detecta la diferencia.

Dos advertencias:

  • Módulo pp no es lo mismo que en los enteros. Si las matrices son de enteros y A⋅BA \cdot B difiere de CC en un múltiplo de pp en cada entrada, módulo pp son iguales y ninguna ronda lo verá. Si lo que interesa es la igualdad en los enteros, hay que elegir pp mayor que cualquier diferencia posible. En el laboratorio el problema se plantea directamente módulo pp, y esa dificultad no aparece.
  • El argumento de las parejas no usa que pp sea primo. Solo usa que dijd_{ij} no es cero módulo pp: funciona con cualquier módulo. Que pp sea primo importa en una variante más fuerte, la del ejercicio 8, en la que las coordenadas de rr se eligen entre los pp restos y no solo entre 0 y 1.

En C++. Con p<230p < 2^{30}, dos restos se multiplican sin overflow en 64 bits: el producto es menor que 2602^{60}. En 32 bits no cabe. mul_mod de freivalds.h recibe y devuelve std::uint64_t y hace a * b % p. El error típico es guardar las entradas en un int o un std::uint32_t y escribir a * b sin convertir antes: C++ multiplica en el tipo de los operandos, y el resultado ya llega dañado a la variable de 64 bits. Con un primo cercano a 2612^{61} ni siquiera 64 bits alcanzan para el producto.

Repetir para bajar el error

Equivocarse la mitad de las veces parece inútil. No lo es, por dos razones: el error está de un solo lado, y se puede repetir.

algoritmo freivalds_repetido(A, B, C, k)
    repetir k veces
        si freivalds(A, B, C) = "distintos" entonces
            devolver "distintos"
        fin si
    fin repetir
    devolver "iguales"
fin algoritmo

Cada ronda lanza monedas nuevas. Si A⋅B=CA \cdot B = C, todas las rondas dicen “iguales” y la respuesta es correcta. Si A⋅B≠CA \cdot B \neq C, el algoritmo se equivoca solo si fallan las kk rondas. Cada una falla con probabilidad a lo sumo 1/21/2, y son independientes, así que

Pr⁡[fallan las k rondas]  ≤  12⋅12⋯12⏟k veces  =  2−k.\Pr[\text{fallan las } k \text{ rondas}] \;\leq\; \underbrace{\tfrac{1}{2} \cdot \tfrac{1}{2} \cdots \tfrac{1}{2}}_{k \text{ veces}} \;=\; 2^{-k}.

El costo es kk veces el de una ronda: O(k⋅n2)O(k \cdot n^2).

El programa freivalds_experiment lo mide. Arma dos matrices de 30×3030 \times 30 al azar y una CC que difiere de A⋅BA \cdot B en una sola entrada, el peor caso. Para cada kk corre el algoritmo 1000 veces y cuenta cuántas responde “iguales”. La semilla del generador es fija, así que la tabla sale igual cada vez que se corre.

$ build/freivalds_experiment
n = 30, p = 1000000007, semilla = 2015, 1000 ejecuciones por fila
C difiere de A·B solo en la entrada (18, 5).

 k   fallos   fracción   cota 2^-k
 1      508      0.508    0.500000
 2      245      0.245    0.250000
 5       34      0.034    0.031250
10        1      0.001    0.000977

Con C = A·B y k = 10: 0 respuestas "distintos" en 1000 ejecuciones.

Con una sola entrada distinta, la probabilidad de fallar es exactamente 2−k2^{-k}, y en 1000 ejecuciones se esperan cerca de 1000⋅2−k1000 \cdot 2^{-k} fallos: 500, 250, 31 y 1. Salieron 508, 245, 34 y 1. No son los números exactos porque es un experimento: si lanzan 1000 monedas, que salgan 508 caras no sorprende a nadie. Con otra semilla salen otros números igual de cercanos; prueben build/freivalds_experiment 7. La última línea muestra el otro lado: cuando el producto es correcto, el algoritmo no se equivoca nunca.

Gráfico de la fracción de ejecuciones que fallan contra k, la cantidad de rondas, de 1 a 10, con el eje vertical en escala logarítmica de 1 a 0,001. Una recta que baja une los valores de la cota 2^-k: cada ronda la divide entre 2. Sobre ella, cuatro puntos con lo medido en el experimento, con n = 30, una sola entrada distinta y la semilla 2015: con k = 1, 508 fallos de 1000, donde se esperan 500; con k = 2, 245, donde se esperan 250; con k = 5, 34, donde se esperan 31; y con k = 10, 1, donde se espera 1. Los cuatro puntos caen casi sobre la recta.Gráfico de la fracción de ejecuciones que fallan contra k, la cantidad de rondas, de 1 a 10, con el eje vertical en escala logarítmica de 1 a 0,001. Una recta que baja une los valores de la cota 2^-k: cada ronda la divide entre 2. Sobre ella, cuatro puntos con lo medido en el experimento, con n = 30, una sola entrada distinta y la semilla 2015: con k = 1, 508 fallos de 1000, donde se esperan 500; con k = 2, 245, donde se esperan 250; con k = 5, 34, donde se esperan 31; y con k = 10, 1, donde se espera 1. Los cuatro puntos caen casi sobre la recta.
En escala logarítmica la cota es una recta: cada ronda más divide el error entre 2. Lo medido la sigue de cerca, con la variación normal de un experimento.

¿Cuántas rondas hacen falta? Depende de qué error se tolere:

kk Cota del error, 2−k2^{-k}
10 ≈10−3\approx 10^{-3}
20 ≈9,5⋅10−7\approx 9{,}5 \cdot 10^{-7}
30 ≈9,3⋅10−10\approx 9{,}3 \cdot 10^{-10}
100 ≈7,9⋅10−31\approx 7{,}9 \cdot 10^{-31}

Para un error menor que 10−910^{-9} bastan 30 rondas, porque 230=1 073 741 824>1092^{30} = 1\,073\,741\,824 > 10^9, y 29 no alcanzan, porque 229<1092^{29} < 10^9. Con 100 rondas, la probabilidad de error es menor que la de que un rayo cósmico cambie un bit de la memoria durante el cálculo, o la de que el procesador tenga un defecto. A esa altura, la respuesta del algoritmo probabilístico es tan confiable como la de cualquier programa que corra en una máquina física.

Error común. Creer que un algoritmo probabilístico “a veces da la respuesta equivocada y no hay nada que hacer”. El error no es un accidente fuera de control: es un número que se elige. Quien corre el algoritmo decide kk, y con eso fija la probabilidad de error tan pequeña como quiera, pagando un factor kk en el tiempo. Lo que no se puede es llevarla exactamente a cero.

En C++. std::mt19937_64 rng(2015) crea un generador con semilla fija: produce siempre la misma secuencia, en cualquier computadora, porque el estándar define el algoritmo. Sirve para que un experimento se pueda repetir y una prueba no falle un día sí y otro no. Las distribuciones, como std::uniform_int_distribution, no tienen esa garantía: cada biblioteca puede implementarlas distinto. Por eso freivalds.h saca los bits directamente del generador, con rng() >> 63.

La clase BPP

Freivalds tiene error de un solo lado. La definición general permite que el algoritmo se equivoque en los dos sentidos, con tal de que acierte con una ventaja clara.

Un lenguaje AA está en BPP (tiempo polinomial probabilístico con error acotado, bounded-error probabilistic polynomial time) si existe una máquina de Turing probabilística MM, de tiempo polinomial, tal que para toda cadena ww:

w∈A  ⟹  Pr⁡[M acepta w]≥2/3,w∉A  ⟹  Pr⁡[M rechaza w]≥2/3.\begin{aligned} w \in A &\implies \Pr[M \text{ acepta } w] \geq 2/3, \\ w \notin A &\implies \Pr[M \text{ rechaza } w] \geq 2/3. \end{aligned}

“Tiempo polinomial” quiere decir que todas las ramas se detienen en una cantidad polinomial de pasos. En cada caso la máquina se equivoca con probabilidad a lo sumo 1/31/3.

El problema de Freivalds cabe en la definición. Con dos rondas, si A⋅B=CA \cdot B = C acepta con probabilidad 1, y si A⋅B≠CA \cdot B \neq C rechaza con probabilidad al menos 1−1/4=3/4≥2/31 - 1/4 = 3/4 \geq 2/3. Pero no es un buen ejemplo de lo que BPP agrega, porque ese lenguaje ya estaba en P: multiplicar y comparar es polinomial. Freivalds muestra que el azar puede acelerar, de n3n^3 a n2n^2. El ejemplo de la sección siguiente es de otro tipo: un problema para el que no se conoce ningún algoritmo polinomial sin azar.

La constante no importa: amplificación

¿Por qué 1/31/3? Por nada en especial. Cualquier constante menor que 1/21/2 define la misma clase, porque el error se puede bajar repitiendo. Con error de los dos lados ya no sirve “si alguna ronda dice distintos”: hay que correr el algoritmo kk veces, con kk impar, y responder lo que diga la mayoría.

Lema de amplificación. Si un algoritmo se equivoca con probabilidad a lo sumo 1/31/3 en cada ejecución, la mayoría de kk ejecuciones independientes se equivoca con probabilidad a lo sumo

(89)k/2.\left(\tfrac{8}{9}\right)^{k/2}.

No lo demostraremos; el ejercicio 9 da los pasos. La cota baja exponencialmente con kk: con k=12mk = 12m ejecuciones el error es menor que 2−m2^{-m}, porque (8/9)6<1/2(8/9)^6 < 1/2. Así, un número polinomial de repeticiones da un error exponencialmente pequeño, y el tiempo total sigue siendo polinomial.

El programa majority_table calcula la probabilidad exacta de que la mayoría se equivoque, cuando cada ejecución falla con probabilidad exactamente 1/31/3, y la pone al lado de la cota.

$ build/majority_table
  k   la mayoría se equivoca   cota (8/9)^(k/2)
  1                3.333e-01          9.428e-01
  5                2.099e-01          7.449e-01
 11                1.221e-01          5.232e-01
 25                4.151e-02          2.294e-01
 51                6.888e-03          4.961e-02
101                2.724e-04          2.611e-03
201                5.531e-07          7.231e-06

La cota es holgada, y aun así alcanza. Comparen con Freivalds, donde 20 rondas daban un error de una millonésima: con error de los dos lados hacen falta unas 200 ejecuciones para lo mismo. La mayoría converge más lento que “basta un testigo”, pero converge igual de seguro.

Lo que no se puede amplificar es un algoritmo que acierta con probabilidad exactamente 1/21/2. Eso es lanzar una moneda sin mirar la entrada, y la mayoría de muchas monedas sigue siendo una moneda.

Idea clave. En BPP el error es un parámetro, no un defecto. Con error 1/31/3 por ejecución, repetir y votar lo lleva por debajo de cualquier número que se pida, con un costo polinomial.

Identidad de polinomios

Segundo ejemplo, y el más importante de la clase. El problema: dados dos polinomios, ¿son el mismo?

Si los dos vienen escritos por sus coeficientes, se comparan los coeficientes y listo. La dificultad aparece cuando un polinomio viene como una fórmula, con sumas y productos sin desarrollar. Por ejemplo:

f(x)=(x−1)(x−2)(x−3)⋯(x−10).f(x) = (x - 1)(x - 2)(x - 3) \cdots (x - 10).

Desarrollar este producto es posible, pero con varias variables se vuelve inmanejable: el producto (x1+y1)(x2+y2)⋯(xn+yn)(x_1 + y_1)(x_2 + y_2) \cdots (x_n + y_n) se escribe con nn factores y, desarrollado, tiene 2n2^n términos. Evaluar la fórmula en un punto, en cambio, es fácil: nn sumas y n−1n - 1 multiplicaciones.

De ahí la idea, que es la misma de Freivalds: en vez de comparar los objetos, comparar lo que valen en un punto al azar.

algoritmo identidad(f, g)
    r ← un elemento al azar de {0, 1, ..., p - 1}
    si f(r) = g(r) módulo p entonces
        devolver "coinciden"
    sino
        devolver "distintos"
    fin si
fin algoritmo

Como antes, “distintos” es una respuesta segura: se encontró un punto donde difieren. El error posible es responder “coinciden” cuando son distintos, por haber caído justo en un punto donde coinciden. ¿Cuántos puntos así puede haber?

Teorema. Sea pp un primo, y sean ff y gg dos polinomios distintos en una variable, de grado a lo sumo dd, con coeficientes módulo pp. Entonces f(r)=g(r)f(r) = g(r) módulo pp para a lo sumo dd de los pp valores de rr. Por lo tanto, el algoritmo se equivoca con probabilidad a lo sumo d/pd/p.

Demostración. La diferencia h=f−gh = f - g es un polinomio no nulo de grado a lo sumo dd, y f(r)=g(r)f(r) = g(r) exactamente cuando rr es una raíz de hh. Un polinomio no nulo de grado a lo sumo dd tiene a lo sumo dd raíces: por cada raíz aa se le puede sacar un factor (x−a)(x - a), y cada factor baja el grado en uno. Como rr se elige entre pp valores igualmente probables, la probabilidad de caer en una raíz es a lo sumo d/pd/p. ∎

Aquí sí hace falta que pp sea primo. “Sacar un factor por cada raíz” usa que, módulo pp, un producto solo es cero si alguno de los factores lo es, y eso es falso con un módulo compuesto: módulo 6, el polinomio 2x2x tiene grado 1 y dos raíces, 0 y 3.

El programa pit_demo hace el experimento con el polinomio ff de arriba, de grado 10. Lo compara con tres polinomios dados por sus coeficientes: su desarrollo correcto, el desarrollo con el coeficiente de x3x^3 cambiado, y el polinomio cero. Primero con un primo pequeño, 101, y después con el de la semana.

$ build/pit_demo
(x - 1)(x - 2)(x - 3)(x - 4) = x^4 - 10x^3 + 35x^2 - 50x + 24
En x = 7: por factores 360, por coeficientes 360

f(x) = (x - 1)(x - 2)···(x - 10), de grado 10

p = 101, 1000 ejecuciones por fila, cota 10/p = 9.90e-02
  f se compara con                            coinciden en    responde "coinciden"
  su desarrollo                               101 de 101      1000 de 1000
  el desarrollo con un coeficiente cambiado     1 de 101        10 de 1000
  el polinomio cero                            10 de 101       102 de 1000

p = 1000000007, 1000 ejecuciones por fila, cota 10/p = 1.00e-08
  f se compara con                            coinciden en    responde "coinciden"
  su desarrollo                               (no se cuenta)  1000 de 1000
  el desarrollo con un coeficiente cambiado   (no se cuenta)     0 de 1000
  el polinomio cero                           (no se cuenta)     0 de 1000

Las dos primeras líneas son un ejemplo para seguir a mano: 6⋅5⋅4⋅3=3606 \cdot 5 \cdot 4 \cdot 3 = 360, y también 2401−3430+1715−350+24=3602401 - 3430 + 1715 - 350 + 24 = 360.

Con p=101p = 101 se pueden probar los 101 puntos, y la columna del medio dice en cuántos coinciden. Con su desarrollo, en todos: es el mismo polinomio. Con el coeficiente cambiado, la diferencia es x3x^3, que solo se anula en 0: coinciden en un punto. Con el polinomio cero coinciden en las raíces de ff, que son 1,2,…,101, 2, \ldots, 10: diez puntos, justo el máximo que permite el teorema. La columna de la derecha es el experimento: 10 y 102 respuestas equivocadas en 1000, cerca de 1000⋅1/101≈101000 \cdot 1/101 \approx 10 y de 1000⋅10/101≈991000 \cdot 10/101 \approx 99.

Un error del 10 % es mucho. Pero miren la cota: d/pd/p. Para bajarla no hace falta repetir: basta agrandar el conjunto del que se elige el punto. Con p=109+7p = 10^9 + 7 la cota es 10−810^{-8}, y en 1000 ejecuciones no hubo ningún error.

Con varias variables el resultado es el mismo. Se enuncia sin demostración:

Teorema (Schwartz-Zippel). Sea ff un polinomio no nulo en las variables x1,…,xnx_1, \ldots, x_n, de grado total a lo sumo dd, con coeficientes módulo un primo pp. Si r1,…,rnr_1, \ldots, r_n se eligen al azar, de forma independiente y uniforme, en {0,1,…,p−1}\{0, 1, \ldots, p - 1\}, entonces

Pr⁡[f(r1,…,rn)=0]  ≤  dp.\Pr[f(r_1, \ldots, r_n) = 0] \;\leq\; \frac{d}{p}.

El grado total de un término es la suma de sus exponentes, y el de un polinomio es el mayor entre sus términos. Lo notable es que la cota no depende de la cantidad de variables. El teorema de una variable es el caso n=1n = 1.

Con eso, el problema de decidir si dos fórmulas con sumas y productos describen el mismo polinomio módulo pp, con pp mayor que el triple del grado, está en BPP: el grado de una fórmula no pasa de su tamaño, evaluar es polinomial, y el error es a lo sumo d/p<1/3d/p < 1/3. Y aquí está la diferencia con Freivalds: no se conoce ningún algoritmo determinista de tiempo polinomial para este problema. Es el ejemplo estándar de un problema que está en BPP y que no se sabe si está en P.

En la práctica. Comparar dos objetos grandes a través de un valor pequeño calculado con un punto al azar es una técnica de todos los días. Si en Algoritmos vieron la búsqueda de un patrón con hashing (Rabin-Karp), era esto: una cadena se lee como los coeficientes de un polinomio, y su hash es el polinomio evaluado en un punto, módulo un primo. Dos cadenas distintas chocan solo si el punto es raíz de la diferencia. Las bibliotecas de criptografía hacen algo parecido para decidir si un número de cientos de cifras es primo: usan la prueba de Miller-Rabin, que es probabilística, y repiten hasta que el error sea despreciable.

Dónde queda BPP

Teorema. P⊆BPP⊆PSPACE\mathsf{P} \subseteq \mathsf{BPP} \subseteq \mathsf{PSPACE}.

Demostración. P⊆BPP\mathsf{P} \subseteq \mathsf{BPP}: una máquina determinista es una máquina probabilística que nunca lanza una moneda. Acepta con probabilidad 1 o con probabilidad 0, y nunca se equivoca.

BPP⊆PSPACE\mathsf{BPP} \subseteq \mathsf{PSPACE}: sea MM una máquina probabilística de tiempo nkn^k. En cada rama lanza a lo sumo nkn^k monedas. Una máquina determinista recorre todas las cadenas rr de nkn^k bits, una por una; para cada una simula a MM usando los bits de rr como monedas, y cuenta cuántas cadenas llevan a aceptar. Acepta si son al menos dos tercios del total. La simulación de una rama usa espacio polinomial, la cadena rr y el contador ocupan nkn^k bits cada uno, y el espacio se reutiliza entre una cadena y la siguiente. Es la misma idea con la que se mostró que NP⊆PSPACE\mathsf{NP} \subseteq \mathsf{PSPACE}, contando en vez de buscar. ∎

La segunda parte dice algo que conviene no perder de vista: el azar no cambia lo que se puede calcular. Una máquina con monedas se simula sin monedas, probando todas las secuencias. Lo que está en juego es solo el costo: esa simulación tarda un tiempo exponencial.

Lo que no se sabe:

  • Si P=BPP\mathsf{P} = \mathsf{BPP}.
  • Cómo se compara BPP con NP. No se sabe si BPP⊆NP\mathsf{BPP} \subseteq \mathsf{NP}, ni si NP⊆BPP\mathsf{NP} \subseteq \mathsf{BPP}. Lo segundo se cree falso: querría decir que los problemas NP-completos se resuelven en la práctica.

Y lo que se cree: que P=BPP\mathsf{P} = \mathsf{BPP}. Es al revés que con P y NP, donde se cree que son distintas. Hay dos razones.

  • La experiencia. Durante décadas, el ejemplo de un problema en BPP sin algoritmo polinomial conocido fue decidir si un número es primo. En 2002, Agrawal, Kayal y Saxena dieron un algoritmo determinista de tiempo polinomial. Varios otros problemas siguieron el mismo camino.
  • Teoremas condicionales. Se ha demostrado que, si existen problemas que de verdad requieren recursos exponenciales, en un sentido preciso que usa circuitos y que no vimos, entonces se pueden fabricar de manera determinista secuencias de bits que ningún algoritmo eficiente distingue del azar, y con ellas reemplazar las monedas de cualquier algoritmo de BPP. Casi todos creen que esos problemas difíciles existen.

Si es así, el azar no agrega poder: todo lo que se hace en tiempo polinomial con monedas se haría también sin ellas. Seguiría siendo útil en la práctica, porque los algoritmos con azar suelen ser más simples y más rápidos: Freivalds gana un factor nn, y no tiene diez líneas.

Lo que sigue abierto

Las cuatro preguntas con las que el curso termina sin respuesta, y lo que cambiaría con cada una.

P frente a NP. ¿Todo problema cuyas soluciones se comprueban rápido se resuelve rápido?

  • Si P=NP\mathsf{P} = \mathsf{NP}: SAT y todos los problemas NP-completos tendrían algoritmos polinomiales. Encontrar sería tan fácil como comprobar. La criptografía de clave pública que se usa hoy dejaría de ser segura, al menos en principio, porque romperla es un problema de NP. Cuánto cambiaría en la práctica dependería del algoritmo: uno de tiempo n100n^{100} no cambia nada.
  • Si P≠NP\mathsf{P} \neq \mathsf{NP}, que es lo que casi todos creen: se confirmaría que para los problemas NP-completos no hay atajo general. Lo valioso sería la demostración, que tendría que usar una técnica que hoy no existe. No alcanzaría, por sí sola, para garantizar criptografía segura: eso pide problemas difíciles en casi todas las entradas, y no solo en el peor caso.

NP frente a coNP. ¿Toda fórmula insatisfacible tiene una demostración corta de que lo es?

  • Si NP=coNP\mathsf{NP} = \mathsf{coNP}: existirían certificados cortos para el “no”. Habría una demostración de tamaño polinomial de que una fórmula no tiene solución, o de que un grafo no tiene camino hamiltoniano.
  • Si NP≠coNP\mathsf{NP} \neq \mathsf{coNP}: entonces también P≠NP\mathsf{P} \neq \mathsf{NP}. La razón es que P es cerrada bajo complemento: si P fuera igual a NP, NP también sería cerrada bajo complemento, y sería igual a coNP. Por eso separar NP de coNP es al menos tan difícil como separar P de NP.

P frente a PSPACE. ¿Lo que se resuelve con memoria polinomial se resuelve en tiempo polinomial?

  • Si P=PSPACE\mathsf{P} = \mathsf{PSPACE}: entonces también P=NP\mathsf{P} = \mathsf{NP}, porque NP queda en medio. Además, decidir quién gana en un juego como la geografía generalizada sería polinomial.
  • Si P≠PSPACE\mathsf{P} \neq \mathsf{PSPACE}: es lo que se cree, y debería ser más fácil de demostrar que P≠NP\mathsf{P} \neq \mathsf{NP}, porque afirma menos. Tampoco se ha podido. Recuerden que alguna de las inclusiones entre P y EXPTIME es estricta, y no se sabe cuál.

L frente a NL. ¿Hace falta el no determinismo para decidir alcanzabilidad con memoria logarítmica?

  • Si L=NL\mathsf{L} = \mathsf{NL}: PATH se decidiría con espacio logarítmico de forma determinista. Para grafos no dirigidos eso ya se sabe: Reingold lo demostró en 2005. Para grafos dirigidos es la pregunta abierta.
  • Si L≠NL\mathsf{L} \neq \mathsf{NL}: adivinar el camino sería indispensable, y ningún algoritmo determinista decidiría PATH con memoria logarítmica. En espacio se sabe mucho más que en tiempo: Savitch da NL⊆SPACE(log⁡2n)\mathsf{NL} \subseteq \mathsf{SPACE}(\log^2 n), y NL=coNL\mathsf{NL} = \mathsf{coNL}. Aun así, esto falta.

Las cuatro se parecen: en todas se pregunta si un recurso (adivinar, la memoria reutilizable, el certificado del otro lado) agrega poder, en todas se cree que sí, y en ninguna se sabe.

Más allá del curso

Tres temas que continúan lo visto. Cada uno es un curso entero; aquí solo va de qué tratan.

Demostraciones interactivas. NP es la clase de lo que se puede demostrar con un certificado escrito, que un verificador determinista revisa. ¿Qué pasa si el verificador puede lanzar monedas y hacer preguntas a quien demuestra, en varias rondas, y solo se le pide convencerse con alta probabilidad? Esa clase se llama IP. El resultado es sorprendente: IP=PSPACE\mathsf{IP} = \mathsf{PSPACE}, demostrado por Shamir hacia 1990. Con preguntas y azar, un verificador de tiempo polinomial puede quedar convencido de cosas para las que no se conoce ningún certificado corto, como que una fórmula no es satisfacible. La demostración convierte fórmulas en polinomios y usa la idea de la identidad de polinomios de este capítulo. Es, además, un resultado que no relativiza.

Criptografía. Todo el curso trató la dificultad como un obstáculo. La criptografía la usa como materia prima: un cifrado es seguro si romperlo exige resolver un problema difícil. Lo que necesita es una función de un solo sentido: fácil de calcular y difícil de invertir en casi todas las entradas. Si existe alguna, entonces P≠NP\mathsf{P} \neq \mathsf{NP}. No se sabe si existen, y no se sabe si P≠NP\mathsf{P} \neq \mathsf{NP} alcanzaría para que existan. Los sistemas que se usan se apoyan en problemas concretos que se creen difíciles, como factorizar un número. La seguridad de internet descansa, hoy, sobre conjeturas.

Computación cuántica. Una computadora cuántica es otro modelo de máquina, con su propia clase de tiempo polinomial con error acotado, BQP. Se sabe que BPP⊆BQP⊆PSPACE\mathsf{BPP} \subseteq \mathsf{BQP} \subseteq \mathsf{PSPACE}. El resultado más conocido es el algoritmo de Shor, de 1994, que factoriza en tiempo polinomial cuántico, algo que no se sabe hacer con una computadora clásica. Dos precisiones. Primero, una computadora cuántica no calcula nada que una máquina de Turing no pueda: se la puede simular, con un costo exponencial. La tesis de Church-Turing no se toca; lo que está en discusión es el costo. Segundo, no se conoce ningún algoritmo cuántico de tiempo polinomial para un problema NP-completo, y se cree que no existe: para buscar entre 2n2^n candidatos, lo mejor que se conoce baja a unos 2n/22^{n/2} pasos, que sigue siendo exponencial.

El mapa completo del curso

En la semana 1 dijimos que el camino iría de la máquina más simple a la más general, y que a cada modelo se le buscaría el límite. Este es el camino completo. Tiene dos partes: los niveles que dependen de qué máquina hace falta, y, dentro de lo decidible, las clases que dependen de cuántos recursos.

De lo regular a lo no reconocible

Mapa del curso en dos partes. Arriba, cinco regiones, una dentro de otra, cada una con su modelo y con un lenguaje que está en ella y no en la de más adentro. La de afuera, con borde punteado, es todos los lenguajes: la mayoría, porque hay más lenguajes que máquinas; su ejemplo es EQ_TM, que no es reconocible ni tiene complemento reconocible (semana 10). Adentro, los reconocibles: una máquina de Turing acepta las cadenas del lenguaje; su ejemplo es A_TM, que no es decidible, por diagonalización (semana 9). Adentro, los decidibles: una máquina de Turing que siempre se detiene; su ejemplo es a^n b^n c^n, que no es libre de contexto, por bombeo (semana 6). Adentro, los libres de contexto: una gramática o un autómata de pila; su ejemplo es 0^n 1^n, que no es regular, por bombeo o Myhill-Nerode (semana 4). En el centro, los regulares: un DFA, un NFA o una expresión regular; su ejemplo son las cadenas que terminan en 01. Abajo, una franja del mismo color que los decidibles, titulada dentro de los decidibles, por recursos: seis cajas unidas por signos de inclusión, cada una con un problema característico. L con 0^n 1^n, NL con PATH, P con 2-SAT, NP con SAT, PSPACE con TQBF y EXPTIME con A_TM con reloj. Una nota dice que EXPTIME no es todo lo decidible, y otra que los dos mapas se cruzan: todo lenguaje regular está en L, todo libre de contexto está en P, y a^n b^n c^n está en L.Mapa del curso en dos partes. Arriba, cinco regiones, una dentro de otra, cada una con su modelo y con un lenguaje que está en ella y no en la de más adentro. La de afuera, con borde punteado, es todos los lenguajes: la mayoría, porque hay más lenguajes que máquinas; su ejemplo es EQ_TM, que no es reconocible ni tiene complemento reconocible (semana 10). Adentro, los reconocibles: una máquina de Turing acepta las cadenas del lenguaje; su ejemplo es A_TM, que no es decidible, por diagonalización (semana 9). Adentro, los decidibles: una máquina de Turing que siempre se detiene; su ejemplo es a^n b^n c^n, que no es libre de contexto, por bombeo (semana 6). Adentro, los libres de contexto: una gramática o un autómata de pila; su ejemplo es 0^n 1^n, que no es regular, por bombeo o Myhill-Nerode (semana 4). En el centro, los regulares: un DFA, un NFA o una expresión regular; su ejemplo son las cadenas que terminan en 01. Abajo, una franja del mismo color que los decidibles, titulada dentro de los decidibles, por recursos: seis cajas unidas por signos de inclusión, cada una con un problema característico. L con 0^n 1^n, NL con PATH, P con 2-SAT, NP con SAT, PSPACE con TQBF y EXPTIME con A_TM con reloj. Una nota dice que EXPTIME no es todo lo decidible, y otra que los dos mapas se cruzan: todo lenguaje regular está en L, todo libre de contexto está en P, y a^n b^n c^n está en L.
Arriba, qué máquina hace falta; abajo, cuántos recursos. Son dos medidas distintas de los mismos lenguajes decidibles.

Cada nivel contiene al de más adentro, y cada inclusión es estricta: hay un lenguaje que lo demuestra.

Nivel Modelo Un lenguaje que está aquí y no en el nivel anterior Técnica que lo demuestra Semana
Regulares DFA, NFA, expresión regular Las cadenas que terminan en 01\mathtt{01} (se da el autómata) 1 a 3
Libres de contexto Gramática, autómata de pila { 0n1n:n≥0 }\{\, \mathtt{0}^n\mathtt{1}^n : n \geq 0 \,\} Lema de bombeo, o cadenas distinguibles (Myhill-Nerode) 4
Decidibles Máquina de Turing que siempre se detiene { anbncn:n≥0 }\{\, \mathtt{a}^n\mathtt{b}^n\mathtt{c}^n : n \geq 0 \,\} Lema de bombeo para lenguajes libres de contexto 6
Reconocibles Máquina de Turing ATMA_{\mathrm{TM}} Diagonalización 9
Todos los lenguajes Ninguno El complemento de ATMA_{\mathrm{TM}}; EQTM\mathrm{EQ}_{\mathrm{TM}} “Reconocible con complemento reconocible es decidible”; reducción por función 9 y 10

Un párrafo por nivel, con lo que conviene tener a mano.

Regulares. Memoria fija: una cantidad de estados que no depende de la entrada. Tres descripciones equivalentes: DFA, NFA y expresiones regulares (teorema de Kleene), con sus conversiones: la construcción de subconjuntos, la de Thompson y la eliminación de estados. Son cerrados bajo unión, intersección, complemento, concatenación, estrella y reverso. Todo lo que se pregunte sobre un autómata finito es decidible: si acepta una cadena, si su lenguaje es vacío, si dos autómatas son equivalentes. El límite es que no pueden contar sin tope. Para demostrar que un lenguaje no es regular hay dos herramientas. El lema de bombeo, jugado contra un adversario: él elige pp, nosotros la cadena, él la división, nosotros el exponente. Y las cadenas distinguibles: para {0n1n}\{\mathtt{0}^n\mathtt{1}^n\}, las cadenas 0i\mathtt{0}^i son distinguibles dos a dos, porque el sufijo 1i\mathtt{1}^i separa a 0i\mathtt{0}^i de 0j\mathtt{0}^j; son infinitas, y un DFA necesitaría infinitos estados. Las dos son el principio del palomar.

Libres de contexto. Se agrega una pila: memoria sin límite, pero solo se ve la cima. Dos descripciones equivalentes: gramáticas y autómatas de pila. Aquí el no determinismo sí agrega poder: el autómata de pila determinista reconoce menos. Son cerrados bajo unión, concatenación y estrella, y no bajo intersección ni complemento. Decidir si una gramática genera una cadena es decidible, y polinomial, con CYK. Decidir si dos gramáticas son equivalentes, si una genera todas las cadenas o si es ambigua es indecidible. El límite es que una pila compara una sola pareja de cantidades. Para {anbncn}\{\mathtt{a}^n\mathtt{b}^n\mathtt{c}^n\} se usa el lema de bombeo para lenguajes libres de contexto, con s=uvxyzs = uvxyz: los trozos vv e yy no alcanzan a tocar los tres tipos de símbolos, y bombear desequilibra las cantidades.

Decidibles. Una máquina de Turing que se detiene con toda entrada: un algoritmo. Por la tesis de Church-Turing, es lo mismo que “lo que un programa puede resolver”, con cualquier lenguaje de programación y cualquier cantidad de tiempo y memoria. {anbncn}\{\mathtt{a}^n\mathtt{b}^n\mathtt{c}^n\} es decidible: la máquina de la semana 7 tacha un símbolo de cada tipo por vuelta. Son cerrados bajo complemento, porque basta intercambiar aceptar y rechazar. El límite es ATMA_{\mathrm{TM}}: ninguna máquina decide si otra máquina acepta una cadena. La demostración es la diagonal: una máquina DD que hace lo contrario que cada máquina con su propia descripción. Desde ATMA_{\mathrm{TM}} se llega a los demás problemas indecidibles con reducciones: el problema de la parada, ETME_{\mathrm{TM}}, EQTM\mathrm{EQ}_{\mathrm{TM}}, el problema de correspondencia de Post, y, con el teorema de Rice, toda propiedad no trivial del lenguaje de una máquina.

Reconocibles. Una máquina de Turing que acepta las cadenas del lenguaje y que, con las demás, puede rechazar o no detenerse nunca. ATMA_{\mathrm{TM}} es reconocible: la máquina universal simula y acepta si la simulación acepta. Lo mismo el problema de la parada y el de correspondencia de Post: se busca, y si hay respuesta afirmativa se la encuentra. No son cerrados bajo complemento, y esa es la manera de salir de ellos: si un lenguaje y su complemento son reconocibles, el lenguaje es decidible. Como ATMA_{\mathrm{TM}} es reconocible y no decidible, su complemento no es reconocible.

Más allá. Hay lenguajes para los que ni ellos ni su complemento son reconocibles, como EQTM\mathrm{EQ}_{\mathrm{TM}}; se demuestra con dos reducciones por función. Y son la mayoría: las máquinas se pueden listar y los lenguajes no, así que casi todos los lenguajes quedan aquí, aunque cueste nombrar uno.

Dentro de lo decidible: las clases de complejidad

La segunda parte del mapa mide recursos. Todas estas clases están dentro de los lenguajes decidibles.

L⊆NL⊆P⊆NP⊆PSPACE⊆EXPTIME⊊decidibles\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{P} \subseteq \mathsf{NP} \subseteq \mathsf{PSPACE} \subseteq \mathsf{EXPTIME} \subsetneq \text{decidibles}
Clase Recurso Un problema característico Qué se sabe
L Espacio logarítmico, determinista {0n1n}\{\mathtt{0}^n\mathtt{1}^n\}, con dos contadores en binario L≠PSPACE\mathsf{L} \neq \mathsf{PSPACE}. No se sabe si L=NL\mathsf{L} = \mathsf{NL}
NL Espacio logarítmico, no determinista PATH, que es NL-completo NL=coNL\mathsf{NL} = \mathsf{coNL}, NL⊆SPACE(log⁡2n)\mathsf{NL} \subseteq \mathsf{SPACE}(\log^2 n), NL≠PSPACE\mathsf{NL} \neq \mathsf{PSPACE}
P Tiempo polinomial, determinista PATH, 2-SAT, todo lenguaje libre de contexto (CYK) P≠EXPTIME\mathsf{P} \neq \mathsf{EXPTIME}. No se sabe si P=NP\mathsf{P} = \mathsf{NP}
NP Tiempo polinomial, no determinista; o un verificador con certificado SAT, 3-SAT, HAMPATH, CLIQUE, SUBSET-SUM: NP-completos (los dos últimos, por las reducciones de Algoritmos) No se sabe si NP=coNP\mathsf{NP} = \mathsf{coNP} ni si NP=PSPACE\mathsf{NP} = \mathsf{PSPACE}
coNP Los complementos de los lenguajes de NP Las fórmulas insatisfacibles P⊆NP∩coNP\mathsf{P} \subseteq \mathsf{NP} \cap \mathsf{coNP}
BPP Tiempo polinomial con monedas, error a lo sumo 1/31/3 Identidad de polinomios P⊆BPP⊆PSPACE\mathsf{P} \subseteq \mathsf{BPP} \subseteq \mathsf{PSPACE}. Se cree que P=BPP\mathsf{P} = \mathsf{BPP}
PSPACE Espacio polinomial TQBF, geografía generalizada: PSPACE-completos PSPACE=NPSPACE\mathsf{PSPACE} = \mathsf{NPSPACE} (Savitch)
EXPTIME Tiempo exponencial ATMrelojA_{\mathrm{TM}}^{\mathrm{reloj}}, que es EXPTIME-completo P≠EXPTIME\mathsf{P} \neq \mathsf{EXPTIME}

Tres cosas para leer bien esta tabla.

Los dos mapas se cruzan. Las clases de complejidad no son “niveles más finos” del primer mapa. Todo lenguaje regular está en L, y todo lenguaje libre de contexto está en P. Pero {anbncn}\{\mathtt{a}^n\mathtt{b}^n\mathtt{c}^n\}, que no es libre de contexto, está en L: tres contadores en binario alcanzan. Que un lenguaje pida un modelo más general no quiere decir que cueste más.

Lo que se sabe es poco. Inclusiones: todas las de la cadena. Igualdades: PSPACE=NPSPACE\mathsf{PSPACE} = \mathsf{NPSPACE} y NL=coNL\mathsf{NL} = \mathsf{coNL}. Separaciones: las cinco de la tabla de pares, que salen de los teoremas de jerarquía, y la última de la cadena, que también: por el teorema de jerarquía de tiempo hay lenguajes decidibles que no están en EXPTIME. Nada más.

Lo que no se sabe se organiza con reducciones. Sin poder separar las clases, lo que el área sí puede hacer es comparar problemas. Un problema completo para una clase es el más difícil de ella: si SAT está en P, entonces P=NP\mathsf{P} = \mathsf{NP}; si TQBF está en P, entonces P=PSPACE\mathsf{P} = \mathsf{PSPACE}; si PATH está en L, entonces L=NL\mathsf{L} = \mathsf{NL}. Cada pregunta abierta sobre clases es una pregunta sobre un problema concreto.

Las cuatro técnicas

Todo el curso se hizo con cuatro ideas, que vuelven con distinta ropa.

Técnica La idea Dónde apareció
Simulación Una máquina imita a otra Construcción de subconjuntos; una cinta por varias; la máquina universal; NP⊆PSPACE\mathsf{NP} \subseteq \mathsf{PSPACE}; Savitch; BPP⊆PSPACE\mathsf{BPP} \subseteq \mathsf{PSPACE}
Palomar Con memoria finita, algo se repite, y lo repetido se puede bombear Los dos lemas de bombeo; Myhill-Nerode; “una máquina que se detiene no repite configuraciones”
Diagonalización Una máquina que hace lo contrario que cada una de una lista Hay más lenguajes que máquinas; ATMA_{\mathrm{TM}}; los teoremas de jerarquía
Reducción Si AA se resuelve con BB, entonces BB es al menos tan difícil como AA Indecidibilidad (semana 10); NP-completitud (semana 13); PSPACE-completitud (semana 14); EXPTIME (hoy)

Las simulaciones dan inclusiones: lo que se puede. El palomar y la diagonal dan los límites: lo que no se puede. Las reducciones llevan un límite de un problema a otro, y siempre en la misma dirección: para demostrar que BB es difícil, se reduce desde un problema que ya se sabe difícil hacia BB.

Idea clave. Para ubicar un lenguaje en el mapa hacen falta dos argumentos. Uno de pertenencia, que es una máquina o un algoritmo: “está en este nivel porque esto lo decide”. Y uno de exclusión, que es una de las técnicas de límite: “no está en el nivel anterior por bombeo, por diagonalización o por reducción”. En el examen se piden los dos.

El código de la semana

Todo está en code/week-15. Dentro del entorno del curso:

make        # compila los programas en build/
make test   # corre las pruebas
Archivo Qué es
freivalds.h Matrices módulo pp, mul_mod, el producto exacto y el algoritmo de Freivalds con kk rondas
freivalds_demo.cpp El ejemplo de 3×33 \times 3, con los 8 vectores
freivalds_experiment.cpp La tabla de fallos para k=1,2,5,10k = 1, 2, 5, 10, con semilla fija
pit.h, pit_demo.cpp Polinomios módulo pp y la prueba de identidad en un punto al azar
majority.h, majority_table.cpp La probabilidad exacta de que la mayoría de kk ejecuciones se equivoque
diagonal.h, diagonal_demo.cpp La tabla de la diagonal con seis decididores
test_*.cpp Las pruebas

Las pruebas comprueban lo que este capítulo afirma con números:

  • test_freivalds verifica el teorema sin azar: para cientos de matrices pequeñas prueba los 2n2^n vectores y comprueba que, si A⋅B≠CA \cdot B \neq C, al menos la mitad detecta la diferencia, y que si A⋅B=CA \cdot B = C ninguno lo hace. Lo repite con varios módulos, también con el 6, que no es primo. Comprueba los conteos 4, 4 y 7 del ejemplo, y que con una sola entrada distinta detectan exactamente los vectores con un 1 en esa columna. Por último vuelve a correr el experimento con la semilla 2015 y exige los números de la tabla: 508, 245, 34 y 1.
  • test_pit comprueba el desarrollo de (x−1)(x−2)(x−3)(x−4)(x - 1)(x - 2)(x - 3)(x - 4), que las dos formas de un polinomio coinciden en todos los puntos, los conteos 101, 1 y 10 con p=101p = 101, y los de la tabla del experimento.
  • test_majority comprueba los valores exactos para k=1,3,5k = 1, 3, 5, que se pueden calcular a mano, que la cota (8/9)k/2(8/9)^{k/2} se cumple para todo kk impar hasta 301, y los números de la tabla.
  • test_diagonal comprueba que la fila de DD difiere de cada una de las seis en la casilla de la diagonal.
$ make test
test_freivalds: correcto
test_pit: correcto
test_majority: correcto
test_diagonal: correcto
Todas las pruebas pasaron.

Que una prueba de un algoritmo con azar sea determinista no es una contradicción. Con la semilla fija, el generador produce siempre los mismos bits, y el experimento es un cálculo como cualquier otro. Lo que la prueba fija es “con estas monedas sale 508”. El teorema, que habla de todas las monedas, se prueba aparte, contando vectores.

El laboratorio

En lab/freivalds está el enunciado, un esqueleto y los casos. La entrada es nn y tres matrices de n×nn \times n con entradas en {0,…,p−1}\{0, \ldots, p - 1\}, con p=109+7p = 10^9 + 7, y la salida es iguales o distintos según A⋅BA \cdot B sea o no igual a CC módulo pp.

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

Se resuelve con Freivalds repetido 30 veces, que da un error menor que 10−910^{-9} por caso. Hay tres cosas que cuidar. La primera es el overflow: el producto de dos entradas no cabe en 32 bits, y hay casos con entradas iguales a p−1p - 1 hechos para notarlo. La segunda es no “ahorrarse” el azar: hay casos en los que comparar las sumas de las filas, que es Freivalds con el vector de solo unos, no ve la diferencia. La tercera es el tiempo: en los dos casos grandes n=2000n = 2000, y calcular A⋅BA \cdot B con n3n^3 multiplicaciones no termina dentro del límite. La lectura de la entrada ya viene escrita en el esqueleto, porque son 12 millones de números y leerlos mal cuesta más que todo el algoritmo.

Los pasos 4 y 5 del laboratorio son el experimento de este capítulo, hecho con su propio código: en el archivo experiment.cpp pegan su función de una ronda, y el programa mide cuántas veces fallan k=1k = 1, 2, 5 y 10 rondas en 1000 ejecuciones.

Resumen

  • Las inclusiones de la cadena L⊆NL⊆P⊆NP⊆PSPACE⊆EXPTIME\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{P} \subseteq \mathsf{NP} \subseteq \mathsf{PSPACE} \subseteq \mathsf{EXPTIME} se demuestran con simulaciones. Una separación pide un lenguaje y un argumento sobre todas las máquinas de una clase: una diagonal.
  • Una función ff es construible en espacio si f(n)f(n) se puede calcular en espacio O(f(n))O(f(n)). Las funciones usuales lo son.
  • Teorema de jerarquía de espacio: para ff construible existe un lenguaje decidible en espacio O(f(n))O(f(n)) y no en espacio o(f(n))o(f(n)). La máquina DD, con la entrada ⟨M⟩10k\langle M \rangle \mathtt{1}\mathtt{0}^k, simula a MM dentro de f(n)f(n) celdas y responde lo contrario.
  • La diagonal con recursos necesita tres cosas más que la de la semana 9: la función construible, para fijar el límite; el relleno 10k\mathtt{1}\mathtt{0}^k, para que cada máquina se enfrente a una entrada lo bastante larga; y un contador de pasos, para cortar a las máquinas que no se detienen.
  • Teorema de jerarquía de tiempo: para tt construible existe un lenguaje decidible en tiempo O(t(n))O(t(n)) y no en tiempo o(t(n)/log⁡t(n))o(t(n) / \log t(n)). El factor log⁡t(n)\log t(n) es lo que cuesta llevar el contador.
  • Los teoremas dicen que existe algún lenguaje al que más recursos le sirven. No dicen que a todo problema le sirvan, ni cuánto cuesta un problema dado.
  • Se sabe: P≠EXPTIME\mathsf{P} \neq \mathsf{EXPTIME}, NL≠PSPACE\mathsf{NL} \neq \mathsf{PSPACE} y L≠PSPACE\mathsf{L} \neq \mathsf{PSPACE} (este con Savitch), y por lo tanto también L≠EXPTIME\mathsf{L} \neq \mathsf{EXPTIME} y NL≠EXPTIME\mathsf{NL} \neq \mathsf{EXPTIME}. De los otros diez pares de la cadena no se sabe nada. Al menos una de las inclusiones entre P y EXPTIME es estricta, y no se sabe cuál.
  • Hay problemas que no están en P por teorema: los EXPTIME-completos, como decidir si una máquina acepta en a lo sumo kk pasos con kk en binario.
  • ✂️ Con un oráculo las máquinas consultan gratis un lenguaje. Existen AA y BB con PA=NPA\mathsf{P}^A = \mathsf{NP}^A y PB≠NPB\mathsf{P}^B \neq \mathsf{NP}^B. Una demostración que relativiza, como la diagonalización por simulación, no puede resolver P frente a NP.
  • Una máquina probabilística lanza monedas. La probabilidad se calcula sobre las monedas, para cada entrada; la entrada no es al azar.
  • Freivalds comprueba A⋅B=CA \cdot B = C con tres productos de matriz por vector, O(n2)O(n^2). Si A⋅B≠CA \cdot B \neq C, al menos la mitad de los vectores de ceros y unos lo detecta: se emparejan los vectores que difieren en una coordenada. El error es de un solo lado, y con kk rondas es a lo sumo 2−k2^{-k}.
  • BPP: tiempo polinomial con error a lo sumo 1/31/3 de cada lado. La constante no importa: la mayoría de kk ejecuciones se equivoca con probabilidad a lo sumo (8/9)k/2(8/9)^{k/2}.
  • Identidad de polinomios: dos polinomios distintos de grado a lo sumo dd coinciden en a lo sumo dd puntos módulo un primo pp, así que un punto al azar los distingue salvo con probabilidad d/pd/p. Está en BPP y no se sabe si está en P.
  • P⊆BPP⊆PSPACE\mathsf{P} \subseteq \mathsf{BPP} \subseteq \mathsf{PSPACE}. El azar no cambia lo que se puede calcular, y se cree que tampoco lo que se puede calcular en tiempo polinomial: P=BPP\mathsf{P} = \mathsf{BPP}.
  • Abierto: P frente a NP, NP frente a coNP, P frente a PSPACE, L frente a NL.
  • El mapa: regulares ⊊\subsetneq libres de contexto ⊊\subsetneq decidibles ⊊\subsetneq reconocibles ⊊\subsetneq todos los lenguajes, separados por {0n1n}\{\mathtt{0}^n\mathtt{1}^n\}, {anbncn}\{\mathtt{a}^n\mathtt{b}^n\mathtt{c}^n\}, ATMA_{\mathrm{TM}} y el complemento de ATMA_{\mathrm{TM}}, con el lema de bombeo, el lema de bombeo para lenguajes libres de contexto, la diagonalización y las reducciones.

Ejercicios

  1. Digan cuáles de estas afirmaciones se siguen de los teoremas de jerarquía, y con qué funciones: (a) SPACE(n)⊊SPACE(nlog⁡n)\mathsf{SPACE}(n) \subsetneq \mathsf{SPACE}(n \log n); (b) TIME(n2)⊊TIME(n2log⁡n)\mathsf{TIME}(n^2) \subsetneq \mathsf{TIME}(n^2 \log n); (c) TIME(n2)⊊TIME(n2log⁡2n)\mathsf{TIME}(n^2) \subsetneq \mathsf{TIME}(n^2 \log^2 n); (d) TIME(2n)⊊TIME(3n)\mathsf{TIME}(2^n) \subsetneq \mathsf{TIME}(3^n); (e) SPACE(n2)⊊SPACE(2n2)\mathsf{SPACE}(n^2) \subsetneq \mathsf{SPACE}(2n^2). En las que no se siguen, digan qué hipótesis falla.
  2. En la máquina DD del teorema de jerarquía de espacio, digan qué deja de funcionar en la demostración con cada cambio: (a) se quita la etapa 3 y se simula a MM con la entrada ⟨M⟩\langle M \rangle, sin relleno; (b) se quita el contador de pasos; (c) en la etapa 4 se simula a MM con la entrada ⟨M⟩\langle M \rangle en vez de con ww completa. En cada caso, señalen la frase de la demostración que ya no vale.
  3. Sea f(n)=n2f(n) = n^2 y sea MM una máquina que usa espacio g(n)=50 nlog⁡2ng(n) = 50\, n \log_2 n y a la que DD simula con d=4d = 4. Encuentren un n0n_0 tal que la simulación quepa en f(n)f(n) celdas para todo n≥n0n \geq n_0. Si ∣⟨M⟩∣=1000|\langle M \rangle| = 1000, ¿cuántos ceros de relleno alcanzan?
  4. Demuestren que NP≠SPACE(n)\mathsf{NP} \neq \mathsf{SPACE}(n). No se pide decir cuál contiene a cuál, que no se sabe. Pista: NP es cerrada bajo reducciones en tiempo polinomial; muestren con un relleno que, si SPACE(n)\mathsf{SPACE}(n) lo fuera, contendría a SPACE(n2)\mathsf{SPACE}(n^2).
  5. Demuestren que PSPACE≠EXPSPACE\mathsf{PSPACE} \neq \mathsf{EXPSPACE}, donde EXPSPACE=⋃kSPACE(2nk)\mathsf{EXPSPACE} = \bigcup_k \mathsf{SPACE}(2^{n^k}). Después expliquen por qué el mismo argumento no separa P de NP: ¿qué tendría que poder hacer la máquina DD?
  6. Con las matrices AA y BB del ejemplo y la matriz CC que es igual a A⋅BA \cdot B salvo que la entrada (3,1)(3, 1) vale 6 en vez de 4, hagan a mano la tabla de los 8 vectores. ¿Cuáles detectan la diferencia? Emparejen los vectores como en la demostración. Comprueben modificando freivalds_demo.cpp.
  7. Den matrices AA, BB y CC de 2×22 \times 2, con A⋅B≠CA \cdot B \neq C, para las que exactamente 3 de los 4 vectores detecten la diferencia. ¿Puede haber un caso en que detecten los 4? ¿Por qué?
  8. La variante con rr en todo el rango. Supongan que cada coordenada de rr se elige al azar, de forma independiente y uniforme, en {0,1,…,p−1}\{0, 1, \ldots, p - 1\}, con pp primo. Demuestren que, si A⋅B≠CA \cdot B \neq C módulo pp, la probabilidad de no detectarlo es a lo sumo 1/p1/p. Pista: agrupen los vectores de a pp, los que solo difieren en la coordenada jj, y usen que la ecuación dij⋅rj+s=0d_{ij} \cdot r_j + s = 0 tiene exactamente una solución módulo pp. ¿Dónde se usa que pp es primo? Den un ejemplo con módulo 6 en el que la cota 1/61/6 falle.
  9. El lema de amplificación. Sea ε≤1/3\varepsilon \leq 1/3 la probabilidad de error de una ejecución, y kk impar. (a) Una secuencia concreta de kk resultados con ii errores tiene probabilidad εi(1−ε)k−i\varepsilon^i (1 - \varepsilon)^{k - i}. Muestren que, si i>k/2i > k/2, eso es a lo sumo (ε(1−ε))k/2(\varepsilon (1 - \varepsilon))^{k/2}. (b) Hay a lo sumo 2k2^k secuencias. Concluyan que la mayoría se equivoca con probabilidad a lo sumo (4ε(1−ε))k/2≤(8/9)k/2(4 \varepsilon (1 - \varepsilon))^{k/2} \leq (8/9)^{k/2}. (c) ¿Cuántas ejecuciones garantiza la cota para un error menor que 10−910^{-9}? Compárenlo con build/majority_table.
  10. ¿Cuántas rondas de Freivalds hacen falta para que el error sea menor que 10−910^{-9}? ¿Y menor que 10−1810^{-18}? Si se corre el algoritmo con k=30k = 30 sobre un millón de casos distintos con A⋅B≠CA \cdot B \neq C, den una cota para la probabilidad de que falle en alguno. Pista: la probabilidad de que ocurra alguno de varios eventos es a lo sumo la suma de sus probabilidades.
  11. Usen la prueba de identidad para decidir si (x+1)8=x8+8x7+28x6+56x5+70x4+56x3+28x2+8x+1(x + 1)^8 = x^8 + 8x^7 + 28x^6 + 56x^5 + 70x^4 + 56x^3 + 28x^2 + 8x + 1 sin desarrollar el lado izquierdo: evalúen los dos lados en x=2x = 2 y en x=10x = 10. Si coinciden en esos dos puntos, ¿queda demostrada la igualdad? ¿En cuántos puntos distintos habría que evaluar para tener una demostración, y por qué?
  12. Ubiquen cada lenguaje en el mapa completo: digan el nivel más pequeño al que pertenece y justifiquen la pertenencia y la exclusión, nombrando la técnica. (a) { w#w:w∈{0,1}∗ }\{\, w\mathtt{\#}w : w \in \{\mathtt{0}, \mathtt{1}\}^* \,\}; (b) las cadenas binarias con igual cantidad de ceros y de unos; (c) { ⟨M⟩:M acepta alguna cadena }\{\, \langle M \rangle : M \text{ acepta alguna cadena} \,\}; (d) { ⟨M⟩:M no acepta ninguna cadena }\{\, \langle M \rangle : M \text{ no acepta ninguna cadena} \,\}; (e) { ⟨M,w⟩:M acepta w en a lo sumo ∣w∣2 pasos }\{\, \langle M, w \rangle : M \text{ acepta } w \text{ en a lo sumo } |w|^2 \text{ pasos} \,\}; (f) las fórmulas booleanas que son tautologías. Para los decidibles, digan además la clase de complejidad más pequeña del curso en la que saben ponerlos.
  13. Para programar. Agreguen a freivalds.h la variante del ejercicio 8, con las coordenadas de rr en {0,…,p−1}\{0, \ldots, p - 1\}, y repitan el experimento de freivalds_experiment con un módulo pequeño, p=5p = 5, para poder ver los fallos. Con una sola entrada distinta, ¿qué fracción de fallos esperan con k=1k = 1 y con k=2k = 2? ¿Y con p=109+7p = 10^9 + 7?
  14. Para programar. Escriban una prueba de identidad para polinomios en dos variables dados como sumas de productos de factores de la forma (ax+by+c)(a x + b y + c), módulo p=109+7p = 10^9 + 7. Úsenla para comprobar que (x+y)(x−y)=x2−y2(x + y)(x - y) = x^2 - y^2 y para detectar que (x+y)2≠x2+y2(x + y)^2 \neq x^2 + y^2. Según el teorema de Schwartz-Zippel, ¿qué probabilidad de error tiene cada ejecución?