PPP (complejidad)

En la teoría de la complejidad computacional , la clase de complejidad PPP ( principio del palomar polinomial ) es una subclase de TFNP . Es la clase de problemas de búsqueda que pueden demostrarse como totales mediante una aplicación del principio del palomar . Christos Papadimitriou la introdujo en el mismo artículo que introdujo PPAD y PPA. ^{[ 1 ]} PPP contiene tanto PPAD como PWPP (principio del palomar débil polinomial) como subclases. Estas clases de complejidad son de particular interés en criptografía porque están fuertemente relacionadas con primitivas criptográficas como permutaciones unidireccionales y funciones hash resistentes a colisiones .

PPP es el conjunto de todos los problemas de cálculo de funciones que admiten una reducción en tiempo polinomial al problema PIGEON , definido de la siguiente manera:

Dado un circuito booleano${\displaystyle C}$tener el mismo número${\displaystyle n}$de bits de entrada como bits de salida, encontrar una entrada${\displaystyle x}$que se asigna a la salida${\displaystyle C(x)=0^{n}}$o dos entradas distintas${\displaystyle x\neq y}$que se asignan a la misma salida${\displaystyle C(x)=C(y)}$.

Un problema es PPP- completo si PIGEON también es reducible a él en tiempo polinomial. Nótese que el principio del palomar garantiza que PIGEON es total. También podemos definir WEAK-PIGEON , para el cual el principio del palomar débil garantiza la totalidad. PWPP es la clase correspondiente de problemas que son reducibles a él en tiempo polinomial. ^{[ 2 ]} WEAK-PIGEON es el siguiente problema:

Dado un circuito booleano${\displaystyle C}$teniendo${\displaystyle n}$bits de entrada y${\displaystyle n-1}$bits de salida, encontrar${\displaystyle x\neq y}$de tal manera que${\displaystyle C(x)=C(y)}$.

Aquí, el rango del circuito es estrictamente menor que su dominio, por lo que se garantiza que el circuito no es inyectivo . WEAK-PIGEON se reduce a PIGEON agregando un solo bit 1 a la salida del circuito, por lo que PWPP${\displaystyle \subseteq }$PPP.

El problema PIGEON ordinario puede verse de forma equivalente como encontrar una colisión en un mapa de${\displaystyle N+1}$palomas a${\displaystyle N}$agujeros. Esto se ha generalizado a colisiones múltiples. Para un entero${\displaystyle t\geq 2}$, el problema${\displaystyle t}$-PIGEON pregunta, dado un circuito booleano que representa un mapa de${\displaystyle (t-1)N+1}$palomas a${\displaystyle N}$agujeros, para encontrar${\displaystyle t}$Palomas distintas asignadas al mismo agujero. La clase asociada${\displaystyle t}$-PPP consiste en problemas de búsqueda NP totales reducibles a este problema;${\displaystyle 2}$-PPP coincide con PPP. ^{[ 3 ]}

Jain, Li, Robere y Xun estudiaron estas clases como una jerarquía de principios de palomar generalizados. ^{[ 3 ]} Demostraron que, en el entorno de caja negra, las clases de palomar generalizadas forman una jerarquía estricta y las relacionaron con la resistencia a múltiples colisiones en criptografía. También mostraron que, como consecuencia, RAMSEY (dado un grafo, encontrar una camarilla o conjunto independiente de un tamaño cuya existencia está garantizada) no tiene una reducción de caja negra a PPP. Esto constituyó una evidencia para refutar una conjetura de Goldberg y Papadimitriou de que RAMSEY pertenece a la clase PPP en el modelo de circuito estándar.

Podemos considerar el circuito de PIGEON como una función hash computable en tiempo polinomial. Por lo tanto, PPP es la clase de complejidad que refleja la dificultad de invertir o detectar una colisión en funciones hash. En términos más generales, la relación entre las subclases de FNP y las clases de complejidad en tiempo polinomial puede utilizarse para determinar la existencia de ciertas primitivas criptográficas, y viceversa.

Por ejemplo, se sabe que si FNP = FP , entonces no existen funciones unidireccionales . De manera similar, si PPP = FP, entonces no existen permutaciones unidireccionales. ^{[ 4 ]} Por lo tanto, PPP (que es una subclase de FNP) captura más de cerca la cuestión de la existencia de permutaciones unidireccionales. Podemos demostrar esto reduciendo el problema de invertir una permutación.${\displaystyle \pi }$en una salida${\displaystyle y}$a PALOMA . Construir un circuito${\displaystyle C}$que calcula${\displaystyle C(x)=\pi (x)\oplus y}$. Desde${\displaystyle \pi }$es una permutación, una solución para PIGEON debe generar${\displaystyle x}$de tal manera que${\displaystyle C(x)=0=\pi (x)\oplus y}$, lo cual implica${\displaystyle \pi (x)=y}$.

La resistencia a múltiples colisiones proporciona un análogo criptográfico de los principios generalizados del palomar. Para${\displaystyle t\geq 2}$, a${\displaystyle t}$-función hash resistente a múltiples colisiones (${\displaystyle t}$-MCRH) es una familia de funciones hash con clave decreciente para la cual es computacionalmente inviable encontrar${\displaystyle t}$entradas distintas con la misma salida;${\displaystyle 2}$-MCRH es la resistencia a colisiones ordinaria. El problema de búsqueda asociado es débil.${\displaystyle t}$-problema del palomar de colisión, a menudo denominado${\displaystyle t}$-PWPP, y está estrechamente relacionado con la jerarquía no débil.${\displaystyle t}$-PPP. ^{[ 3 ]}

Jain, Li, Robere y Xun describieron sus separaciones de caja negra entre principios de palomar generalizados como un primer paso hacia la cuestión criptográfica de si la resistencia a múltiples colisiones puede convertirse genéricamente en resistencia a colisiones ordinarias. ^{[ 3 ]} El trabajo posterior de Mao y Zhang resolvió la versión de paso adyacente de caja negra completa de esta cuestión: para cada constante${\displaystyle t\geq 3}$, no hay una construcción de caja negra de${\displaystyle (t-1)}$-MCRH de${\displaystyle t}$-MCRH. ^{[ 5 ]} Bajo la traducción habitual entre construcciones criptográficas de caja negra completa y reducciones de Turing de caja negra aleatorias entre los problemas de búsqueda asociados, esto descarta la reducción correspondiente de la${\displaystyle t}$-problema de palomar de colisión para el${\displaystyle (t-1)}$-problema de colisión; en particular, descarta una construcción de caja negra completa del hash resistente a colisiones ordinario a partir del hash 3-multi-resistente a colisiones. ^{[ 5 ]}

PPP contiene PPAD como una subclase (la contención estricta es un problema abierto ). Esto se debe a que End-of-the-Line , que define PPAD, admite una reducción directa en tiempo polinomial a PIGEON . En End-of-the-Line , la entrada es un vértice de inicio.${\displaystyle s}$en un grafo dirigido${\displaystyle G}$donde cada vértice tiene como máximo un sucesor y como máximo un predecesor, representados por una función sucesora computable en tiempo polinomial.${\displaystyle f}$Defina un circuito${\displaystyle C}$cuya entrada es un vértice${\displaystyle x}$y cuyo resultado es su sucesor, si lo hay, o${\displaystyle x}$si no lo hace. Si representamos el vértice fuente${\displaystyle s}$como la cadena de bits${\displaystyle 0^{n}}$, este circuito es una reducción directa de End-of-the-Line a Pigeon , ya que cualquier colisión en${\displaystyle C}$proporciona un fregadero en${\displaystyle G}$.