PCP-teorem

I kompleksitetsteori , et felt med teoretisk informatikk , er PCP-teoremet ( akronym for engelsk sannsynlig kontrollerbart bevis , som kan oversettes på fransk som "  bevis verifiserbart i sannsynlighet  ") en karakterisering av klassen NP i sammenheng med et interaktivt bevis systemet . Mer presist, NP er klassen av beslutningsproblemer som har bevis som kan verifiseres sannsynlig ved å ha tilgang til et konstant antall bits av beviset og ved å bruke et logaritmisk antall tilfeldige bits.

PCP-teoremet er veldig viktig i teoretisk informatikk: det bringer mange inkludert om vanskeligheten med å tilnærme de algoritmiske problemene .

Uformell presentasjon

PCP-teoremet sier at hvis man tolererer en feilmargin, er det ikke nødvendig å lese et helt bevis for å være overbevist om at det er riktig. Vi kan omformulere denne påstanden også som følger: det eksisterer en konstant K slik at ethvert matematisk bevis P på lengde n kan skrives om til et bevis P ' med polynomlengde i n , slik at det er tilstrekkelig å bare undersøke K- symboler på P' ( ved hjelp av en randomisert algoritme ) for å bli overbevist om bevisets 99% nøyaktighet.

"Jam jam"


Under sitt plenumsforelesning på 2010 International Congress of matematikere , Irit Dinur brukte en analogi til å formidle dette teoremet. Det rapporteres i disse vilkårene av Étienne Ghys  :

"Det er som om du har en brødskive som kanskje har en liten dråpe syltetøy et sted, men du vet ikke hvor." Du tar en bit av skålen, tilfeldig, og du finner ikke syltetøy; kan du utlede at det ikke er syltetøy i det hele tatt? Definitivt ikke, med mindre du prøver mye. Men hvis du begynner med å spre syltetøyet på brødskiven med en kniv, vil den bli funnet over alt, og du trenger bare å ta en prøve for å finne ut om det var en dråpe syltetøy. Her er det det samme. Vi starter fra et bevis P som har et sted, kanskje en feil. Det er en måte å "spre" beviset for å bygge en annen P " der feilene, hvis noen, har" spredt seg "overalt, og de er nå enkle å oppdage ved å ta en liten bit. Antall prøver. "

PCP-system

Vurder problemet med å verifisere et bevis for en matematisk teorem. Siden bevisene kan være lange og vanskelige å verifisere i sin helhet, kan man lete etter en måte å presentere et bevis på slik at det er tilstrekkelig å verifisere bare en liten del av det for å bedømme teoremets gyldighet med et rimelig nivå av tillit. Student. Dette spørsmålet er adressert av bevis som kan verifiseres på en sannsynlig måte .

Uformelt, en sannsynlighet Verifiserbar Proof (PCP) system for et språk er en polynomisk tid sannsynlighetskontrollør Dette ordet, kalt orakel , representerer bevis og blir bare delvis undersøkt av verifisereren. Spørsmålene til oraklet er posisjoner i det binære ordet og myntkastene, som muligens kan avhenge av svarene på tidligere spørsmål. Det er verifisereren som bestemmer om en gitt oppføring tilhører språket. Hvis oppføringen er på språket, blir det bedt om at verifisereren alltid godtar ordet, forutsatt at det er utstyrt med et passende orakel. Med andre ord avviser revisor aldri et ord som står på språket. Hvis ikke ordet ikke er på språket, avviser verifikatoren det med en sannsynlighet større enn halvparten, uavhengig av hvilket orakel som brukes.

Vi kan se PCP-systemer når det gjelder interaktive proof-systemer . Vi betrakter deretter oraklet som en bevist (som ønsker å bevise påstanden), og spørsmålene som så mange meldinger sendt til det av bekrefteren. I sammenheng med PCP blir Prover sett på som å ikke ha noe minne om de forrige spørsmålene, og tar derfor ikke med i svarene spørsmålene som ble stilt tidligere.

En mer interessant tolkning er å se PCP-systemer som en generalisering av verifikatorer for NP-klassen. I stedet for å utføre en polynomisk tidsberegning ved mottak av det komplette beviset (som i tilfelle en verifikator for et NP-problem), har verifisereren lov til å vende en mynt og undersøke beviset bare på de stedene det velger. Dette gjør det mulig å inspisere lange bevis, ikke se på mer enn et bestemt polynomielt antall steder, eller tilsvarende se på veldig få biter av et bevis.

Det er bemerkelsesverdig at PCP-systemer tillater å fullt ut karakterisere språk i NP . Denne karakteriseringen har vist seg å være nyttig av sammenhengen som er etablert mellom vanskeligheten med å tilnærme noen NP-harde problemer og spørsmålet om likhet mellom P og NP. Med andre ord er ikke-tilnærmelsesresultater for forskjellige klassiske optimaliseringsproblemer etablert ved bruk av PCP-systemer for språk i NP-klassen.

Stater

Sannsynlige bevis gir kompleksitetsklasser i henhold til antall spørsmål som kreves og hvor mye tilfeldighet som er brukt. Klassen PCP [ r (n), q (n) ] refererer til settet med avgjørelsesproblemer som har verifiserbare bevis med sannsynlighet som kan oppfylles i polynomet med høyst r (n) tilfeldige biter og ved å lese på pluss q ( n) bevisbiter. Som allerede nevnt ovenfor, bør korrekte bevis alltid aksepteres og feil bevis skal avvises med sannsynligheten på minst 1/2. PCP-setningen sier det

PCP [O (log n ), O (1)] = NP .

Demonstrasjon

Et bevis på et svakere resultat, NP = PCP [n 3 , 1], blir gitt i et av Dexter Kozens kurs.

Søknad til tilnærmelsesalgoritmer

PCP-teoremet har viktige konsekvenser innen tilnærmelsesalgoritmer . Spesielt tjener det til å vise at MAX-3SAT og Maximum Independent Set-problemer, blant andre, ikke kan tilnærmes effektivt, med mindre P = NP .

MAX-3SAT eksempel

MAX-3SAT-problemet er som følger: gitt en 3CNF-formel, dvs. i konjunktiv normal form , hvor hver ledd inneholder maksimalt 3 liter (som i 3-SAT-problemet ), hva er det maksimale antall ledd som kan oppfylles ved samme tildeling av variabler?

Tilnærmet vanskelighetsresultat er som følger:

Det er en slik konstant at eksistensen av en tilnærmelsesalgoritme for MAX-3SAT med tilnærmelsesforhold , innebærer at P = NP.

Dette er faktisk en følge av følgende setning:

Det er en konstant slik at det for ethvert språk er en funksjon som går fra strenger til 3CNF-formler slik at de innebærer at alle ledd av kan oppfylles, og antyder at den tilfredsstillende leddfraksjonen av er mindre enn .

Historie og betydning

Teoremets historie begynner i 1980, med arbeid med påvist null kunnskap om kunnskap ( null kunnskapssikker ) av Goldwasser, Micali og Rackoff. Disse resultatene har på forhånd ingenting å gjøre med tilnærmingen, men introdusere ideen om bevismester og verifikator. Koblingen mellom beviskontroll og tilnærming ble laget tidlig på 1990-tallet av Feige, Goldwasser, Lovász, Safra og Szegedy.

I 2001 mottok Sanjeev Arora , Uriel Feige , Shafi Goldwasser , Carsten Lund , László Lovász , Rajeev Motwani , Shmuel Safra , Madhu Sudan og Mario Szegedy den prestisjetunge Gödelprisen for sine papirer om PCP-teoremet ( Feige et al. 1996 ) ( Arora og Safra 1998 ) ( Arora et al. 1998 ).

I 2006 publiserte Irit Dinur et helt nytt bevis på den kombinatoriske teoremet, særlig ved bruk av utvidelsesdiagrammer ( Dinur 2007 ). Dette bevis gjorde at han fikk 2019 Gödel Prize .

Ingo Wegener sa om denne teoremet at det var "det viktigste resultatet i kompleksitetsteori siden Cooks teorem  ". For Oded Goldreich er det "kulminasjonen av en serie imponerende verk, rike på innovasjoner".

Bibliografi

Artikler

Popularisering

Eksterne linker

(fr) PCP-klassen i Complexity Zoo

Merknader og referanser

  1. Bernard H. Korte og Jens Vygens ( trans.  Jean FONLUPT og Alex Skoda), kombi optimalisering: Teori og algoritmer , Springer-Verlag ,2010( les online ) , s.  443
  2. Init Dinurs plenarforelesning er tilgjengelig på hans personlige side på Probabilistically Checkable Proofs (survey and talk) .
  3. I vilkårene for rapporten publisert i ( Ghys 2010 ).
  4. Christian Scheideler, “  Computational Models  ” (åpnet 16. juli 2013 ) .
  5. (i) Dexter C. Közen , Theory of Computation , London, Springer-Verlag , al.  "Tekster innen informatikk",2006, 119–127  s. ( ISBN  978-1-84628-297-3 , les online )
  6. (in) Sanjeev Arora og Boaz Barak , Computational Complexity: A Modern Approach , Cambridge University Press ,2009( ISBN  0-521-42426-7 ) , kap.  11.2.2 ("PCP and hardness of approximation")
  7. Dana Moshkovitz, “  The tale of the PCP theorem  ”, ACM Crossroads , vol.  18 n o  3, 2012, s.  23-26 ( les online )
  8. Offisiell side av 2001 Gödel-prisen
  9. Gödelpris 2009-siden, for sikksakkproduktet av grafer, hvis siste avsnitt gjelder beviset for Dinur
  10. "  Gödelprisen 2019  " , på EATCS (åpnet 9. august 2020 ) .
  11. "  Det viktigste resultatet i kompleksitetsteori siden Cooks teorem  " i: (en) Ingo Wegener, Complexity Theory: Exploring the Limits of Efficient Algorithms , Springer,2005, 308  s. ( ISBN  978-3-540-21045-0 , leses online ) , s.  161.
  12. "  En kulminasjon av en sekvens av imponerende verk [...] rik på innovative ideer  " i: (en) Oded Goldreich, Computational Complexity: A Conceptual Perspective , Cambridge, Cambridge University Press ,2008, 606  s. ( ISBN  978-0-521-88473-0 , leses online ) , s.  405.
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">