El problema P = NP plantea: “Si podemos verificar rápidamente que la solución a un problema es correcta, ¿podemos también calcular rápidamente la solución?”. La mayoría de los investigadores creen que la respuesta es no, es decir, P ≠ NP.

Al comprender el problema P vs NP, podemos ver cómo las Zero Knowledge Proofs (ZKPs) encajan en el campo más amplio de las ciencias de la computación y comprender qué pueden y qué no pueden hacer las ZKPs.

Es mucho más fácil “entender” las Zero Knowledge Proofs relacionándolas con el problema P vs NP.

Este tutorial tiene tres partes:

1. Explicar el problema P vs NP
2. Expresar problemas y soluciones como una fórmula booleana
3. P vs NP y cómo se relacionan con las Zero Knowledge Proofs

Requisitos previos

Asumimos que el lector está familiarizado con la complejidad temporal y la notación $\mathcal{O}$ grande.

Decimos que un algoritmo toma tiempo polinómico si se ejecuta en tiempo $\mathcal{O}(nᶜ)$ o más rápido, donde $n$ es el tamaño de la entrada y $c$ es una constante no negativa. Podemos referirnos a los algoritmos que se ejecutan en tiempo polinómico o más rápido como algoritmos eficientes porque su tiempo de ejecución no crece demasiado rápido con el tamaño de la entrada.

Decimos que un algoritmo toma tiempo exponencial o es costoso si se ejecuta en $\mathcal{O}(cⁿ)$ donde $c$ es una constante mayor que 1 y $n$ es el tamaño de la entrada porque el algoritmo se vuelve exponencialmente lento a medida que aumenta el tamaño de la entrada.

Parte 1: Explicar el problema P vs NP

Los problemas en P son problemas que son a la vez fáciles de resolver y para los cuales es fácil verificar las soluciones.

Los problemas que pueden resolverse en tiempo polinómico y cuyas soluciones pueden verificarse en tiempo polinómico se denominan problemas en P.

Aquí hay algunos ejemplos de problemas para los que es fácil calcular y verificar soluciones. Estas tareas podrían ser realizadas por diferentes partes, una haciendo el cálculo y otra comprobando que los resultados sean válidos:

Ejemplo 1 de P: Ordenar una lista

Podemos ordenar eficientemente una lista y podemos verificar eficientemente que una lista está ordenada.

• Resolución: Ordenar la lista toma tiempo $\mathcal{O}(n \log n)$ (por ejemplo, usando mergesort), lo cual es tiempo polinómico. Aunque $n \log n$ no es un polinomio, sabemos que $\log n < n$ y por lo tanto $(n \log n) < n²$, por lo que el tiempo de ejecución de nuestro algoritmo está acotado superiormente por algún polinomio, que es el requisito para el “tiempo polinómico”.

• Verificación: Podemos verificar que la lista está ordenada recorriéndola y comprobando que cada elemento es mayor que su vecino de la izquierda, lo cual tomaría tiempo $\mathcal{O}(n)$.

Ejemplo 2 de P: Devolver el índice de un número en una lista, si aparece en la lista

Podemos buscar eficientemente para ver si un número está en una lista y luego verificar aún más eficientemente que el número está presente si conocemos el índice en el que se encuentra.

• Resolución: Por ejemplo, dada la lista [8, 2, 1, 6, 7, 3], necesitamos tiempo $\mathcal{O}(n)$ para determinar si el número 7 está en la lista.

• Verificación: Pero si te damos la lista y decimos que el 7 está en el índice 4, puedes verificar que el número está en la lista en esa posición en tiempo $\mathcal{O}(1)$. Buscar un elemento, si no se nos dice su posición, toma tiempo $\mathcal{O}(n)$ en el caso general ya que tenemos que buscar a través de toda la lista. Si se nos dice la supuesta ubicación del elemento, toma tiempo $\mathcal{O}(1)$ verificar que el elemento está, de hecho, en la lista en esa ubicación.

Ejemplo 3 de P: Determinar si dos nodos en un grafo están conectados

Podemos determinar eficientemente si dos nodos en un grafo están conectados utilizando búsqueda en anchura (breadth-first search) — comenzar en un nodo, luego visitar todos sus vecinos excepto los nodos que ya hemos visitado, luego buscar en los vecinos de los vecinos, y así sucesivamente.

• Resolución: Descubrir la ruta entre los nodos utilizando la búsqueda en anchura tomará tiempo $\mathcal{O}(n + e)$, donde $n$ es el número de nodos en el grafo y $e$ es el número de aristas. El número de aristas $e$ no puede exceder $n^2$, por lo que podemos tratar $\mathcal{O}(n + e)$ como $\mathcal{O}(n²)$ en el peor de los casos.

• Verificación: Podemos verificar que la ruta propuesta es válida en tiempo $\mathcal{O}(n)$ simplemente siguiendo la ruta propuesta para ver si los dos puntos realmente están conectados por esa ruta.

En todos los ejemplos anteriores, tanto el cálculo como la verificación de la solución pueden realizarse en tiempo polinómico.

El Testigo (Witness)

Un testigo (witness) en ciencias de la computación es la prueba de que resolviste el problema correctamente. En los ejemplos anteriores, el testigo es la respuesta correcta al problema. Para los ejemplos anteriores, estas son cosas que podríamos usar como testigo:

1. La lista ordenada
2. El índice donde aparece un número en la lista
3. La ruta entre dos nodos en un grafo

Veremos más adelante que un testigo no tiene que ser necesariamente la solución al problema original. También podría ser una solución para una representación alternativa del mismo problema.

Problemas en PSPACE: No todos los problemas tienen soluciones que puedan verificarse de manera eficiente

Los problemas que requieren recursos exponenciales para resolverse y verificarse se denominan problemas en PSPACE. La razón por la que se llaman PSPACE es que, aunque podrían requerir un tiempo exponencial para resolverse, no requieren necesariamente un espacio de memoria exponencial para ejecutar la búsqueda.

Esta clase de problemas ha sido investigada extensamente, sin embargo, no se ha descubierto ningún algoritmo eficiente para resolverlos. Muchos investigadores creen que simplemente no existe un algoritmo eficiente para resolver estos problemas. Si pudiera descubrirse una solución eficiente a estos problemas, también sería posible reutilizar el algoritmo para romper toda la encriptación moderna y alterar fundamentalmente la computación tal y como la conocemos.

A pesar de los importantes incentivos para encontrar soluciones eficientes a estos problemas, la evidencia sugiere que tales soluciones probablemente no existan. Estos problemas son tan desafiantes que no se puede proporcionar una prueba fácilmente verificable (testigo) incluso si se resuelven correctamente.

Ejemplos de problemas en PSPACE

Ejemplo 1 de PSPACE: Encontrar el movimiento óptimo de ajedrez

Supongamos que le preguntamos a una potente computadora: “Dado este tablero de ajedrez con las piezas en esta posición, ¿cuál es el próximo movimiento óptimo?”

La computadora responde con “mueve el peón negro de f4 a f3.”

¿Cómo puedes confiar en que la computadora te está dando la respuesta correcta?

No hay una forma eficiente de comprobarlo: debes hacer el mismo trabajo que hizo la computadora. Esto implica realizar una búsqueda completa a través de todos los posibles estados futuros del tablero. No hay ningún testigo que la computadora pueda proporcionarnos que nos permita confirmar que “mueve el peón negro de f4 a f3” sea en realidad el siguiente mejor movimiento. De esta manera, la naturaleza de este problema es muy diferente a la de los ejemplos discutidos anteriormente: no podemos verificar eficientemente que el movimiento óptimo afirmado sea el verdadero movimiento óptimo.

En este ejemplo, el “testigo” presentado por la computadora consiste en todos los posibles estados futuros del juego. Sin embargo, el volumen masivo de estos datos hace que sea prácticamente imposible verificar la precisión de la solución de manera eficiente.

Ejemplo 2 de PSPACE: Determinar si las regex (expresiones regulares) son equivalentes

Las dos regex, a+ y aa*, coinciden con las mismas cadenas de texto. Si una cadena coincide con la primera regex, también coincidirá con la segunda, y viceversa.

Sin embargo, comprobar si dos regex arbitrarias son equivalentes toma un tiempo exponencial de cálculo. Incluso si una potente computadora te dijera que coinciden con las mismas cadenas, no hay una prueba corta (testigo) que la computadora pueda darte para demostrar que las respuestas son correctas. Al igual que en el ejemplo del ajedrez, tendrías que buscar en un espacio muy grande de cadenas para comprobar si las regex son equivalentes, y eso tomará tiempo exponencial.

Tanto el Ajedrez como la equivalencia de Regex tienen una característica común en que ambos requieren recursos exponenciales para encontrar respuestas y recursos exponenciales para verificar las respuestas.

Problemas aún más intensivos computacionalmente que PSPACE

Hay problemas que son tan difíciles que requieren tiempo exponencial y memoria exponencial para resolverse, pero esos problemas suelen ser teóricos y no aparecen frecuentemente en el mundo real.

Un ejemplo de tal problema son las Damas con una regla que establece que las piezas nunca pueden moverse a una posición que recree un estado anterior del tablero. Para asegurarnos de que no repetimos un estado del tablero para una partida mientras exploramos el espacio de movimientos posibles, tenemos que llevar un registro de todos los estados del tablero que ya han sido visitados. Dado que la duración del juego puede ser exponencial con respecto al tamaño del tablero, los requisitos de memoria también son exponenciales.

Problemas en NP: Algunos problemas pueden verificarse rápidamente pero no resolverse rápidamente

Si podemos verificar rápidamente la solución a un problema, entonces el problema está en NP. Sin embargo, encontrar la solución podría requerir recursos exponenciales.

Cualquier problema cuya solución propuesta (testigo) pueda verificarse rápidamente como correcta es un problema NP. Si el problema también tiene un algoritmo para encontrar la solución en tiempo polinómico, entonces es un problema P. Todos los problemas P son problemas NP, pero es extremadamente improbable que todos los problemas NP sean también problemas P.

Ejemplos de problemas en NP. Estos se explican con más detalle a continuación:

• Calcular la solución de un Sudoku — verificar la solución propuesta para un Sudoku.
• Calcular la 3-coloración de un mapa (si existe) — verificar una 3-coloración propuesta de un mapa.
• Encontrar una asignación para una fórmula booleana que dé como resultado verdadero — verificar que la asignación propuesta hace que la fórmula dé como resultado verdadero.

Nota: NP significa polinómico no determinista (non-deterministic polynomial). No entraremos en la jerga sobre de dónde proviene ese nombre; solo damos el nombre para que el lector no piense equivocadamente que significa “no es tiempo polinómico”.

Ejemplos de problemas en NP

Ejemplo 1 de NP: Sudoku

En el juego de Sudoku, se le da al jugador una cuadrícula de $9 \times 9$ con algunos números completados. El objetivo es que el jugador complete el resto de la cuadrícula con los números del 1 al 9 de tal manera que ningún número aparezca más de una vez en ninguna fila, columna o cuadro de $3 \times 3$ (los delineados con líneas gruesas). Las siguientes imágenes de Wikipedia ilustran esto. En la primera imagen, vemos la cuadrícula de 9x9 tal como se le entrega al jugador. En la segunda imagen, vemos la solución del jugador.

Dada la solución de un Sudoku, podemos verificar rápidamente que la solución es correcta simplemente iterando sobre las columnas, las filas y las subcuadrículas de $3\times 3$. El testigo puede verificarse en tiempo polinómico.

Sin embargo, calcular la solución requiere significativamente más recursos — hay un número exponencial de combinaciones para buscar. Para una cuadrícula de $9\times 9$, esto no es difícil para una computadora. Sin embargo, si permitimos que el Sudoku sea arbitrariamente grande: cada lado tiene un tamaño $n$, donde $n$ es un múltiplo de 9. En ese caso, la dificultad de encontrar la solución crece exponencialmente con $n$.

Ejemplo 2 de NP: 3-coloración de un mapa

Cualquier mapa 2D de territorios puede ser “coloreado” con solo cuatro colores (véase el teorema de los cuatro colores). Es decir, podemos asignar un color único (uno de cuatro colores) a cada territorio de tal manera que ningún territorio vecino comparta el mismo color. Por ejemplo, la siguiente imagen (de Wikipedia) muestra los Estados Unidos coloreados con cuatro colores: rosa, verde, amarillo y rojo. Tómate un momento para observar y verificar que a ningún par de estados que se tocan se les haya dado el mismo color:

El problema de la 3-coloración pregunta si un mapa se puede colorear usando solo tres colores en lugar de cuatro. Descubrir una 3-coloración (si existe) es un problema de búsqueda computacionalmente intensivo. Sin embargo, verificar una 3-coloración propuesta es fácil: iterar a través de cada una de las regiones y comprobar que ninguna región vecina tenga el mismo color del territorio que se está comprobando actualmente.

Resulta que no es posible aplicar una 3-coloración a los Estados Unidos.

Las razones por las que un mapa en particular no puede ser coloreado con 3 colores varían, pero en el caso de los Estados Unidos, Nevada (la región roja en el mapa a continuación) está rodeada por cinco territorios. Coloreamos Nevada con un color, luego debemos alternar los colores de sus territorios vecinos. Sin embargo, cuando terminemos de rodear a los vecinos de Nevada, terminaremos con un territorio que tiene vecinos con tres colores en sus fronteras, sin dejar un color válido para el territorio no coloreado.

Aquí tienes un video rápido e interesante sobre mapas de 3-coloración si quieres aprender más sobre este problema.

Sin embargo, es posible aplicar una 3-coloración a Australia:

No todos los mapas pueden ser coloreados con tres colores. Calcular una 3-coloración para un mapa 2D arbitrario, si es que existe, no puede hacerse eficientemente — generalmente requiere una búsqueda de fuerza bruta que puede tomar tiempo exponencial.

Sin embargo, si alguien resuelve una 3-coloración, es fácil verificar su solución.

La relación entre P, NP y PSPACE

Recursos computacionales para cada clase

La tabla a continuación resume los recursos computacionales requeridos para cada clase de problema:

Jerarquía de dificultad entre P, NP y PSPACE

Cualquier problema que requiera recursos exponenciales para verificar su testigo es un problema de PSPACE (o un problema más difícil). Si alguien tiene recursos exponenciales para verificar testigos de problemas de PSPACE, esa persona puede calcular trivialmente soluciones para cualquier problema P o NP. Por lo tanto, todos los problemas P y NP son un subconjunto de los problemas PSPACE, tal como se ilustra en la figura a continuación.

En otras palabras, si tienes una computadora lo suficientemente potente para resolver o verificar una clase de problema en el círculo más grande, puedes resolver o verificar un subconjunto de él:

El problema P vs NP

P es la clase de problemas que pueden resolverse y verificarse eficientemente, mientras que NP es la clase de problemas que pueden verificarse eficientemente. La pregunta “P vs NP” plantea, simplemente, si estas dos clases son la misma.

Si P = NP, significaría que siempre que podamos encontrar un método eficiente para verificar una solución, también podemos encontrar un método eficiente para encontrar esa solución. Recuerda que encontrar una solución es siempre al menos tan difícil como verificarla. (Por definición, resolver un problema incluye encontrar la respuesta correcta, lo que significa que un algoritmo que resuelve el problema también está verificando su respuesta en el proceso).

Si P = NP es cierto, eso significa que existe un algoritmo eficiente para calcular Sudokus (de tamaño arbitrario) y encontrar si existe una 3-coloración. También significa que existe un algoritmo eficiente para romper la mayoría de los algoritmos criptográficos modernos.

Actualmente, sigue sin probarse si P y NP son el mismo conjunto. Aunque se han hecho numerosos intentos de encontrar algoritmos eficientes para los problemas NP, toda la evidencia sugiere que tales algoritmos no existen.

De manera similar, queda abierto si existen soluciones eficientes o mecanismos de verificación para los problemas PSPACE. Aunque los investigadores especulan ampliamente que P ≠ NP y NP ≠ PSPACE, no existe una prueba matemática formal para estas conclusiones. Por lo tanto, a pesar de los extensos esfuerzos, las soluciones eficientes para los problemas NP y los métodos de verificación eficientes para los problemas PSPACE siguen sin ser descubiertos.

Para fines prácticos, podemos asumir que P ≠ NP y NP ≠ PSPACE. De hecho, hacemos implícitamente esa suposición cuando confiamos datos importantes a los algoritmos de criptografía moderna.

Parte 2: Expresar problemas y soluciones como fórmulas booleanas

Lo que une a los problemas P y NP es que su solución puede verificarse rápidamente. Sería extremadamente útil si pudiéramos describir todos esos problemas (P y NP) y sus soluciones en un lenguaje común. Es decir, queremos una codificación del problema que funcione para problemas tan diversos como demostrar que una lista está ordenada, hasta demostrar que se ha resuelto un Sudoku o demostrar que tenemos una 3-coloración.

Verificar una solución a un problema en NP o P puede lograrse verificando una solución a una fórmula booleana que modela el problema.

Lo que queremos decir con “una fórmula booleana que modela el problema” quedará claro a medida que describamos a qué nos referimos con “una solución a una fórmula booleana” y observemos algunos problemas de modelado de ejemplo con fórmulas booleanas.

Soluciones a una fórmula booleana

Para expresar una fórmula booleana, utilizamos el operador $¬$ para el NOT booleano, $∧$ para el AND booleano y $∨$ para el OR booleano. Por ejemplo, $a ∧ b$ se evalúa como verdadero si y solo si $a$ y $b$ son ambos verdaderos. $a ∧ ¬b$ se evalúa como verdadero si y solo si $a$ es verdadero y $b$ es falso.

Supongamos que tenemos un montón de variables booleanas $x₁$, $x₂$, $x₃$, $x₄$ y una fórmula booleana:

La pregunta es: ¿podemos encontrar valores para $x₁, x₂, x₃, x₄$ tales que $out$ sea verdadero? Para la fórmula anterior, podemos. Escribiendo $T$ para verdadero y $F$ para falso, podemos escribir nuestra solución como:

Al sustituir la solución en la fórmula se obtiene:

Eso fue fácil de verificar, pero descubrir la solución para una fórmula booleana muy grande podría requerir tiempo exponencial. Encontrar una solución a una fórmula booleana es un problema NP en sí mismo: puede requerir recursos exponenciales encontrar la solución, pero verificarla se puede hacer en tiempo polinómico.

Pero debemos enfatizar: nuestro uso de fórmulas booleanas no es para resolverlas, solo para verificar soluciones propuestas para ellas.

Todos los problemas en P y NP pueden verificarse transformándolos en fórmulas booleanas y mostrando una solución a la fórmula

En los siguientes ejemplos, la entrada es un problema P o NP y la salida es una fórmula booleana. Si conocemos la solución al problema original, entonces también conoceremos la solución a la fórmula booleana.

Nuestra intención es mostrar que conocemos al testigo del problema original, pero en forma booleana.

Ejemplo 1: comprobar si una lista está ordenada utilizando una fórmula booleana

Consideremos los números binarios de un bit $A$ y $B$. La siguiente tabla de verdad devuelve verdadero cuando $A > B$:

La columna $A > B$ puede ser modelada con la expresión $A ∧ ¬B$, que devuelve verdadero en la única fila donde $A > B$ es uno.

Ahora consideremos una tabla que exprese $A = B$:

La columna $A = B$ puede ser modelada con la expresión $(A ∧ B) ∨ ¬(A ∨ B)$. $(A ∧ B)$ devuelve verdadero cuando $A = 1$ y $B = 1$ y $¬(A ∨ B)$ devuelve verdadero cuando $A$ y $B$ son ambos cero.

Las expresiones para los números de un bit:

serán muy útiles en breve.

Ahora bien, ¿cómo comparamos números binarios de más de un bit?

Comparación binaria por el bit diferente más significativo

Supongamos que empiezas desde el bit más significativo (MSB) situado más a la izquierda de ambos números y te mueves hacia el bit menos significativo (LSB) a la derecha. En el primer bit, donde los dos números difieren:

Si $P$ tiene un valor de $1$ en ese bit y $Q$ tiene un valor de $0$, entonces $P ≥ Q$.
La siguiente animación ilustra el algoritmo detectando que $P ≥ Q$:

Si $P = Q$, entonces todos los bits son iguales. $P = Q$ significa que $P ≥ Q$ también es verdadero:

Si P < Q, lo detectaremos en el primer bit donde Q sea 1 y P sea 0:

Supongamos, sin pérdida de generalidad, que enumeramos los bits en $P$ como $p₄, p₃, p₂, p₁$ y los bits en $Q$ como $q₄, q₃, q₂, q₁$.

Si $P ≥ Q$, entonces una de las siguientes afirmaciones debe ser verdadera:

• $p₄ > q₄$
• $p₄ = q₄$ y $p₃ > q₃$
• $p₄ = q₄$ y $p₃ = q₃$ y $p₂ > q₂$
• $p₄ = q₄$ y $p₃ = q₃$ y $p₂ = q₂$ y $(p₁ > q₁ \text{ o } p₁ = q₁)$

Podemos combinar los puntos en una sola ecuación.

Recordemos nuestras expresiones booleanas que modelaban la igualdad y comparación de un bit:

Podemos sustituir las expresiones para la fórmula $A > B$ y $A = B$ en la ecuación anterior. Para evitar un muro de matemáticas, mostramos las operaciones en formato de video a continuación:

La fórmula booleana final que expresa $P ≥ Q$, para 4 bits, es:

Llamemos “expresión de comparación” a una expresión booleana que compara dos números binarios de la manera descrita anteriormente.

Comprobar si una lista está ordenada

Dada una fórmula booleana para comparar números de un tamaño fijo, podemos aplicar repetidamente la expresión de comparación a cada par de elementos adyacentes en la lista y combinar las expresiones de comparación usando la operación AND. La lista está ordenada si y solo si el AND de todas las expresiones de comparación es verdadero.

Por lo tanto, vemos que un testigo que prueba que una lista está ordenada no tiene por qué ser la lista ordenada. También puede ser la entrada a la fórmula booleana que creamos arriba que hace que la fórmula devuelva verdadero.

Ejemplo 2: Una 3-coloración como fórmula booleana

Volvamos a ver nuestro mapa de Australia:

Para modelar la solución como una fórmula booleana, la fórmula necesita codificar los siguientes hechos:

• Cada territorio tiene uno de tres colores
• Cada territorio tiene un color diferente al de su vecino

Por ejemplo, para decir que Australia Occidental (Western Australia) es verde, azul o roja, necesitamos crear tres variables WESTERN_AUSTRALIA_GREEN, WESTERN_AUSTRALIA_BLUE, WESTERN_AUSTRALIA_RED. Para evitar nombres de variables largos, llamémoslas WA_G, WA_B, y WA_R. Nuestra fórmula booleana es entonces:

Copy
(WA_G ∧ ¬WA_B ∧ ¬WA_R) ∨ (¬WA_G ∧ WA_B ∧ ¬WA_R) ∨ (¬WA_G ∧ ¬WA_B ∧ WA_R)

En otras palabras:

"(Australia Occidental es verde Y Australia Occidental NO es azul Y Australia Occidental NO es roja)

O

(Australia Occidental NO es verde Y Australia Occidental es azul Y Australia Occidental NO es roja)

O

(Australia Occidental NO es verde Y Australia Occidental NO es azul Y Australia Occidental es roja)"

Coloreando la fórmula booleana para darle énfasis:

(WA_G ∧ ¬WA_B ∧ ¬WA_R) ∨ (¬WA_G ∧ WA_B ∧ ¬WA_R) ∨ (¬WA_G ∧ ¬WA_B ∧ WA_R)

Llamemos a la fórmula anterior la restricción de asignación de color.

Usamos variables booleanas para codificar el color asignado a un territorio. Dado que una variable booleana solo puede contener dos valores, pero un territorio puede ser de uno de los tres colores, a cada territorio se le asignan tres variables booleanas, una para cada color. Si a un territorio se le asigna un color en particular, la variable correspondiente se establece en verdadero y las demás se establecen en falso.

La fórmula anterior es verdadera si y solo si al territorio de Australia Occidental se le asigna exactamente un color.

Restricción de color vecino

A continuación, queremos escribir una fórmula que exprese que WA tiene un color diferente al de su vecino. Creamos tres variables para SA (South Australia, Australia Meridional) como lo hicimos para WA. Ahora, nuestra fórmula simplemente dice, “para cada color, WA y SA no son ambos de ese color”. Esto es equivalente a decir “WA y SA no son del mismo color”. Usemos los nombres de variables SA_G, SA_B, y SA_R para referirnos a la asignación de color de Australia Meridional (que limita con Australia Occidental). Usamos la fórmula a continuación para expresar que tienen colores diferentes:

¬(WA_G ∧ SA_G) ∧ ¬(WA_B ∧ SA_B) ∧ ¬(WA_R ∧ SA_R)

En otras palabras:

NO es el caso que (Australia Occidental sea verde Y Australia Meridional sea verde)

Y

NO es el caso que (Australia Occidental sea azul Y Australia Meridional sea azul)

Y

NO es el caso que (Australia Occidental sea roja Y Australia Meridional sea roja)"

La fórmula anterior se cumplirá si y solo si a Australia Occidental y Australia Meridional no se les asignó el mismo color. Llamemos a la fórmula anterior la restricción de frontera.

Necesitamos aplicar la restricción de asignación de color a cada territorio y la restricción de color diferente a cada par de vecinos, para luego hacer un AND con todas las restricciones juntas.

Una fórmula para modelar una 3-coloración de Australia

Ahora mostramos la fórmula booleana final que verifica una 3-coloración válida para Australia. Aquí están los territorios etiquetados:

Primero, asignamos a cada territorio el nombre de una variable:

• WA = Australia Occidental
• SA = Australia Meridional
• NT = Territorio del Norte
• Q = Queensland
• NSW = Nueva Gales del Sur
• V = Victoria

Restricciones de color: Cada uno de los seis territorios tiene exactamente un color:

Restricciones de frontera: Ningún territorio vecino comparte un color

A continuación, iteramos a través de las fronteras y calculamos una restricción de frontera para esos vecinos. El video a continuación muestra el algoritmo en acción. Mostramos el conjunto final de fórmulas para las condiciones de frontera después del video:

7. Australia Occidental y Australia Meridional:

¬(WA_G ∧ SA_G) ∧ ¬(WA_B ∧ SA_B) ∧ ¬(WA_R ∧ SA_R)

8. Australia Occidental y Territorio del Norte:

¬(WA_G ∧ NT_G) ∧ ¬(WA_B ∧ NT_B) ∧ ¬(WA_R ∧ NT_R)

9. Territorio del Norte y Australia Meridional:

¬(NT_G ∧ SA_G) ∧ ¬(NT_B ∧ SA_B) ∧ ¬(NT_R ∧ SA_R)

10. Territorio del Norte y Queensland:

¬(NT_G ∧ Q_G) ∧ ¬(NT_B ∧ Q_B) ∧ ¬(NT_R ∧ Q_R)

11. Australia Meridional y Queensland:

¬(SA_G ∧ Q_G) ∧ ¬(SA_B ∧ Q_B) ∧ ¬(SA_R ∧ Q_R)

12. Australia Meridional y Nueva Gales del Sur:

¬(SA_G ∧ NSW_G) ∧ ¬(SA_B ∧ NSW_B) ∧ ¬(SA_R ∧ NSW_R)

13. Australia Meridional y Victoria:

¬(SA_G ∧ V_G) ∧ ¬(SA_B ∧ V_B) ∧ ¬(SA_R ∧ V_R)

14. Queensland y Nueva Gales del Sur:

¬(Q_G ∧ NSW_G) ∧ ¬(Q_B ∧ NSW_B) ∧ ¬(Q_R ∧ NSW_R)

15. Nueva Gales del Sur y Victoria:

¬(NSW_G ∧ V_G) ∧ ¬(NSW_B ∧ V_B) ∧ ¬(NSW_R ∧ V_R)

Creamos una fórmula booleana haciendo un AND booleano de las 15 fórmulas mencionadas anteriormente. Tener una asignación a las variables que dé como resultado que la expresión booleana sea verdadera equivale a tener una 3-coloración válida de Australia.

En otras palabras, si conocemos una 3-coloración válida para Australia, también conocemos una asignación para la fórmula booleana construida arriba.

La fórmula booleana debe poder construirse en tiempo polinómico

Solo necesitamos tomar un número polinómico de pasos para construir esta fórmula booleana para la 3-coloración. Específicamente, necesitamos:

• 3 restricciones de color por territorio
• Como máximo N restricciones de color vecino por territorio

Es un requisito que los pasos que se den para construir la fórmula booleana se realicen en tiempo polinómico. Si requiere un número exponencial de pasos, entonces la fórmula booleana será exponencialmente grande y el testigo será exponencialmente grande, y no se podrá verificar en tiempo polinómico.

Resumen del uso de expresiones booleanas para modelar problemas y soluciones propuestas

Todos los problemas en P y NP pueden expresarse como una fórmula booleana que devuelve verdadero si conocemos la asignación de variables correspondiente (testigo), lo cual codifica una solución correcta al problema original.

Ahora que tenemos un lenguaje estándar para demostrar eficientemente una solución a un problema, estamos un paso más cerca de un método estándar para demostrar que tenemos una solución a un problema, sin revelar la solución, es decir, Pruebas de Conocimiento Cero (Zero Knowledge Proofs).

Parte 3: P vs NP y pruebas ZK

Cómo se relaciona P = NP con las pruebas ZK

El “conocimiento” en las Zero Knowledge Proofs se refiere al conocimiento del testigo.

Las pruebas ZK se ocupan del aspecto de verificación de la computación. Es decir, dado que has encontrado una solución de Sudoku o una 3-coloración de un mapa, ¿puedes dar a alguien una evidencia (testigo) que le permita verificar eficientemente que tu solución es correcta?

Las pruebas ZK buscan demostrar que conoces al testigo sin revelarlo.

Las ZKPs solo funcionan con problemas en P o NP. No son utilizables para problemas que no podemos verificar de manera eficiente.

Si no tenemos un mecanismo para probar eficientemente que las regex son equivalentes, o que un cierto movimiento en el ajedrez es óptimo, entonces las pruebas ZK no pueden permitirnos mágicamente producir una prueba tan eficiente.

Tanto para los problemas P como para los NP, la verificación de la solución se puede hacer de manera eficiente. ZK permite verificar que la solución es válida mientras oculta los detalles del cálculo. Además, ZK no puede ayudarte a descubrir una solución para un rompecabezas de Sudoku ni a descubrir una 3-coloración de un mapa. Sin embargo, puede ayudarte a demostrarle a otra parte que tienes una solución, si ya la calculaste.

La conexión entre P vs NP y las Zero Knowledge Proofs

Todos los problemas con soluciones que se pueden verificar rápidamente se pueden convertir en una fórmula booleana.

Poder convertir cualquier problema en una fórmula booleana no es un truco para encontrar la respuesta eficientemente. Resolver una expresión booleana arbitraria es un problema NP, y encontrar una solución para ella puede ser difícil.

El tamaño de la fórmula booleana es importante. Volviendo a nuestro ejemplo del ajedrez, si intentas modelar cada estado con una fórmula booleana, entonces el tamaño de tu fórmula será exponencialmente grande. Por lo tanto, los únicos problemas factibles son NP o P, que tienen fórmulas booleanas de tamaño razonable que los modelan.

En la literatura de ZK, a menudo nos referimos a las fórmulas booleanas como circuitos booleanos.

Crear una prueba de conocimiento cero para un problema se reduce a traducir el problema a un circuito, como se demostró al probar una 3-coloración para Australia o validar una lista ordenada. Luego, pruebas que tienes una entrada válida para el circuito (el testigo), lo que finalmente se transforma en una prueba de conocimiento cero.

La capacidad de verificar eficientemente una solución a un problema es un requisito previo para crear una prueba de conocimiento cero de que tienes una solución. Uno debe poder construir un circuito booleano para modelar la solución eficientemente. Sin embargo, para problemas como determinar los movimientos óptimos de ajedrez, que pertenecen a PSPACE, este enfoque resulta en circuitos exponencialmente grandes, haciéndolos poco prácticos.

En conclusión, las pruebas de conocimiento cero son factibles solo para problemas dentro de P y NP, donde la verificación eficiente de la solución es posible. Sin una verificación eficiente, crear una prueba de conocimiento cero para un problema se vuelve inviable.

Aprende más

Consulta el RareSkills ZK Book para más temas sobre pruebas de conocimiento cero.

Detalles técnicos

Algunos conceptos se han simplificado en este artículo para hacerlos lo más comprensibles posible a alguien que los vea por primera vez. La información presentada aquí es suficiente para explicar qué pueden y qué no pueden hacer las pruebas ZK. Para aquellos interesados en profundizar en el tema, aquí hay algunas aclaraciones:

• A un tablero de ajedrez de un tamaño fijo $(8 \times 8)$ no se le puede asignar un nivel de dificultad porque la dificultad del problema no se puede expresar como $\mathcal{O}(f(n))$. Técnicamente, decimos que el ajedrez de un tamaño arbitrario es PSPACE. Puede ser confuso pensar en un tablero de ajedrez de $10 \times 10$, pero uno simplemente puede especificar que los espacios adicionales no tienen ninguna pieza en su posición inicial.

• El ajedrez tiene una regla menos conocida que indica que si no se ha producido ningún movimiento de captura y ningún peón se ha movido en los últimos 50 movimientos, un jugador puede declarar un empate. Esto establece un límite en el espacio de búsqueda que lo coloca en PSPACE. Si se elimina esta regla, entonces esta versión del ajedrez está en EXPSPACE — una categoría de problemas que requiere tiempo exponencial y tamaño de memoria exponencial para ser calculado.

• Algunos problemas NP pueden ser resueltos en tiempo subexponencial, pero para propósitos prácticos, toman tiempo exponencial para ser resueltos. Por ejemplo $\mathcal{O}(2^{\sqrt{n}})$ es técnicamente subexponencial, pero aún así es exponencialmente difícil.

• Existen heurísticas muy potentes para encontrar soluciones a algunos problemas NP. Aunque la 3-coloración toma un tiempo exponencial para resolverse, muchas instancias del problema de tamaño razonable pueden resolverse rápidamente. Por ejemplo, aquí hay problemas de referencia de mapas con 200 territorios y 3-coloraciones válidas. Algoritmos inteligentes son capaces de encontrar la solución sin explorar un espacio de búsqueda exponencialmente grande. Sin embargo, para cualquier heurística diseñada para acelerar la resolución de un problema NP, es posible crear una instancia patológica del problema que esté diseñada para explotar la heurística y volverla inútil. Sin embargo, las heurísticas funcionan bien para la instancia típica de un ejemplo realista del problema.

Publicado originalmente el 10 de abril de 2024