PPP (complejidad)
En la teoría de la complejidad computacional , la clase de complejidad PPP ( principio de casillero polinomial ) es una subclase de TFNP . Es la clase de problemas de búsqueda que se puede demostrar que son totales mediante la aplicación del principio de casillero . Christos Papadimitriou lo presentó en el mismo documento que presentó PPAD y PPA. [1] PPP contiene tanto PPAD como PWPP (principio de casillero 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 yFunciones hash resistentes a colisiones .
PPP es el conjunto de todos los problemas de cálculo de funciones que admiten una reducción de tiempo polinomial al problema PIGEON , definido de la siguiente manera:
Un problema es PPP- completo si PIGEON también es reducible en tiempo polinómico a él. Tenga en cuenta que el principio del casillero garantiza que PIGEON es total. También podemos definir DÉBIL-PALOMA , para lo cual el principio del casillero débil garantiza la totalidad. PWPP es la clase correspondiente de problemas que son reducibles en tiempo polinómico. [2] WEAK-PIGEON es el siguiente problema:
Aquí, el rango del circuito es estrictamente menor que su dominio, por lo que se garantiza que el circuito no será inyectable . WEAK-PIGEON se reduce a PIGEON agregando un solo 1 bit a la salida del circuito, por lo que PWPP PPP.
Podemos ver el circuito en PIGEON como una función hash computable en tiempo polinomial. Por lo tanto, PPP es la clase de complejidad que captura la dureza de invertir o encontrar una colisión en las funciones hash. De manera más general, la relación de las subclases de FNP con las clases de complejidad de tiempo polinómico se puede utilizar para determinar la existencia de ciertas primitivas criptográficas y viceversa.
Por ejemplo, se sabe que si FNP = FP , las funciones unidireccionales no existen. De manera similar, si PPP = FP, entonces no existen permutaciones unidireccionales. [3] Por lo tanto, PPP (que es una subclase de FNP) capta más de cerca la cuestión de la existencia de permutaciones unidireccionales. Podemos probar esto reduciendo el problema de invertir una permutación en una salida a PIGEON . Construya un circuito que calcule . Dado que es una permutación, una solución a PIGEON debe generar tal que , lo que implica .
