PPP (komplexitet)

I beräkningskomplexitetsteori är komplexitetsklassen PPP ( polynomial pigeonhole princip ) en underklass till TFNP . Det är klassen av sökproblem som kan visas vara total genom tillämpning av duvhålsprincipen . Christos Papadimitriou introducerade det i samma tidning som introducerade PPAD och PPA. PPP innehåller både PPAD och PWPP (polynomial weak pigeonhole-princip) som underklasser. Dessa komplexitetsklasser är av särskilt intresse inom kryptografi eftersom de är starkt relaterade till kryptografiska primitiver som enkelriktade permutationer och kollisionsbeständiga hashfunktioner .

Definition

PPP är uppsättningen av alla funktionsberäkningsproblem som tillåter en polynom-tidsreduktion till PIGEON -problemet, definierat enligt följande:

Givet en boolesk krets $C$ som har samma antal $n$ ingångsbitar som utgångsbitar, hitta antingen en ingång $x$ som är mappad till utgången ${ \displaystyle C(x)=0^{n}}$ , eller två distinkta ingångar $x\neq y$ som är mappade till samma utgång $C( x)=C(y)$ .

Ett problem är PPP- komplett om PIGEON också är polynom-tid reducerbar till det. Observera att duvhålsprincipen garanterar att PIGEON är total. Vi kan också definiera SWAG-DUVA , för vilken principen om svagt duvhål garanterar helhet. PWPP är motsvarande klass av problem som är polynom-tid reducerbara till den. SVAG-DUVA är följande problem:

Givet en boolesk krets $C$ med $n$ ingångsbitar och $n-1$ utgångsbitar, hitta $x\neq y$ så att $C(x)=C(y)$ .

Här är kretsens räckvidd strikt mindre än dess domän, så kretsen är garanterat icke- injektiv . WEAK-PIGEON reducerar till PIGEON genom att lägga till en enda 1 bit till kretsens utgång, så PWPP $\subseteq$ PPP.

Anslutning till kryptografi

Vi kan se kretsen i PIGEON som en polynom-tidsberäknad hashfunktion. Därför är PPP komplexitetsklassen som fångar hårdheten av att antingen invertera eller hitta en kollision i hashfunktioner. Mer generellt kan förhållandet mellan subklasser av FNP och polynomtidskomplexitetsklasser användas för att bestämma förekomsten av vissa kryptografiska primitiver och vice versa.

Till exempel är det känt att om FNP = FP , så existerar inte envägsfunktioner . På liknande sätt, om PPP = FP, existerar inte envägs-permutationer. Därför fångar PPP (som är en underklass till FNP) närmare frågan om förekomsten av enkelriktade permutationer. Vi kan bevisa detta genom att minska problemet med att invertera en permutation $\pi$ på en utgång $y$ till PIGEON . Konstruera en krets $C$ som beräknar $C(x)=\pi (x)\oplus y$ . Eftersom $\pi$ är en permutation måste en lösning till PIGEON mata ut $x$ så att $C(x)=0=\pi (x)\oplus y$ , vilket innebär $\pi (x)=y$ .

Förhållande till PPAD

PPP innehåller PPAD som en underklass (strikt inneslutning är ett öppet problem). Detta beror på att End-of-the-Line , som definierar PPAD, medger en enkel polynom-tidsreduktion till PIGEON . I End-of-the-Line är ingången en startpunkt $s$ i en riktad graf $G$ där varje vertex har högst en efterföljare och högst en föregångare, representerad av ett polynom- tidsberäknad efterföljande funktion $f$ . Definiera en krets $C$ vars ingång är en vertex $x$ och vars utgång är dess efterföljare om det finns en, eller $x$ om den inte gör det. Om vi ​​representerar källpunkten $s$ som bitsträngen $0^{n}$ , är denna krets en direkt reduktion av End-of-the-Line till Pigeon , eftersom varje kollision i ${\ displaystyle C}$ ger en sänkning i $G$ .

Anmärkningsvärda problem

Lika summor problem

Problemet med lika summor är följande problem. Givet $n$ positiva heltal som summerar till mindre än $2^{n}-1$ , hitta två distinkta delmängder av heltal som har samma summa. Detta problem finns i PPP, men det är inte känt om det är PPP-komplett.

Problem med begränsat SIS

Problemet med begränsad SIS (kort heltalslösning), som är en generalisering av SIS-problemet från gitterbaserad kryptografi, har visat sig vara komplett för PPP. Före det arbetet var de enda problemen som var kända för att vara kompletta för PPP varianter av PIGEON .

Heltalsfaktorisering

Det finns randomiserade polynom-tidsreduktioner från heltalsfaktoriseringsproblemet till SWAG -DUVA . Dessutom, under den generaliserade Riemann-hypotesen , finns det också deterministiska polynomreduktioner. Det är dock fortfarande ett öppet problem att ovillkorligen visa att heltalsfaktorisering är i PPP.