PCP sætning

I kompleksitetsteori , et felt af teoretisk datalogi , er PCP-sætningen ( akronym for engelsk sandsynligt kontrollerbart bevis , som kan oversættes på fransk som "  bevis, der kan kontrolleres i sandsynlighed  ") en karakterisering af klassen NP i sammenhæng med et interaktivt bevis system . Mere præcist er NP klassen af beslutningsproblemer, der har beviser, der kan verificeres sandsynligt ved at have adgang til et konstant antal bits i beviset og ved at bruge et logaritmisk antal tilfældige bits.

PCP-sætningen er meget vigtig inden for teoretisk datalogi: den bringer mange med om vanskeligheden ved at tilnærme de algoritmiske problemer .

Uformel præsentation

PCP-sætningen siger, at hvis man tolererer en fejlmargin, er det nytteløst at læse et helt bevis for at være overbevist om dets rigtighed. Vi kan omformulere denne udsagn også som følger: der findes en konstant K, således at ethvert matematisk bevis P af længde n kan omskrives til et bevis P ' af polynomiel længde i n , så det er tilstrækkeligt kun at undersøge K symboler på P' ( ved hjælp af en randomiseret algoritme ) for at blive overbevist om bevisets 99% nøjagtighed.

"Jam shot"


I løbet af sin plenum forelæsning på 2010 Internationale Kongres Matematikere , Irit Dinur brugte en analogi til at formidle denne sætning. Det rapporteres i disse vilkår af Étienne Ghys  :

"Det er som om du har et stykke brød, der måske har en lille dråbe syltetøj et eller andet sted, men du ved ikke hvor." Du tager et stykke af skålen tilfældigt, og du kan ikke finde marmelade; kan du udlede, at der slet ikke er syltetøj? Bestemt ikke, medmindre du laver meget prøveudtagning. Men hvis du starter med at sprede marmeladen på brødskiven med en kniv, vil den findes overalt, og du skal bare tage en prøve for at finde ud af, om der var en dråbe marmelade eller ej. Her er det den samme ting. Vi starter fra et bevis P, som måske har et eller andet sted en fejl. Der er en måde at 'sprede' beviset for at opbygge et andet P ' , hvor eventuelle fejl har' spredt 'sig overalt, og de er nu lette at opdage ved at tage en lille smule. Antal prøver. "

PCP-system

Overvej problemet med at verificere et bevis for en matematisk sætning. Da beviserne kan være lange og vanskelige at verificere i deres helhed, kan man se efter en måde at fremlægge et bevis på, så det er tilstrækkeligt kun at verificere en lille del af det for at bedømme sætningen med et rimeligt niveau af tillid Studerende. Dette spørgsmål behandles af bevissystemer, der kan verificeres på en sandsynlig måde .

Uformelt er et sandsynlighedsverificerbart bevis (PCP) -system for et sprog en polynomisk tids probabilistisk verifikator, der har direkte adgang til de enkelte bits i et binært ord. Dette ord, kaldet oracle , repræsenterer bevis og vil kun blive delvist undersøgt af verifikatoren. Spørgsmålene til oraklet er positioner i det binære ord og møntkast, som muligvis kan afhænge af svarene på tidligere forespørgsler. Det er verifikatoren, der beslutter, om en given post hører til sproget. Hvis posten er på sproget, anmodes det om, at verifikatoren altid accepterer ordet, forudsat at det er forsynet med et passende orakel. Med andre ord afviser revisor aldrig et ord, der er på sproget. Ellers, hvis ordet ikke findes på sproget, afviser verifikatoren det med en sandsynlighed større end en halv, uanset det anvendte orakel.

Vi kan se PCP-systemer i form af interaktive proof-systemer . Vi anser derefter oraklet som et prover (som ønsker at bevise sætningen), og de spørgsmål som så mange beskeder sendt til den af verifikatoren. I forbindelse med PCP ses Prover som intet hukommelse for de tidligere spørgsmål og tager derfor ikke i sine svar hensyn til de tidligere stillede spørgsmål.

En mere interessant fortolkning er at se PCP-systemer som en generalisering af verifikatorer til NP-klassen. I stedet for at udføre en polynomisk tidsberegning efter modtagelse af det komplette bevis (som i tilfælde af en verifikator for et NP-problem), har verifikatoren lov til at vende en mønt og kun undersøge bevis på de steder, som det vælger. Dette giver det mulighed for at inspicere lange bevis, ikke se på mere end et bestemt polynomisk antal placeringer eller tilsvarende se på meget få bits af et bevis.

Det er bemærkelsesværdigt, at PCP-systemer gør det muligt fuldt ud at karakterisere sprog i NP . Denne karakterisering har vist sig at være nyttig ved forbindelsen, der er etableret mellem vanskeligheden ved at tilnærme nogle NP-hårde problemer og spørgsmålet om lighed mellem P og NP. Med andre ord er ikke-tilnærmelsesresultater for forskellige klassiske optimeringsproblemer blevet etableret ved hjælp af PCP-systemer til sprog i NP-klassen.

Stater

Sandsynlige beviser giver anledning til kompleksitetsklasser alt efter antallet af spørgsmål, der kræves, og mængden af ​​tilfældighed, der er brugt. Klassen PCP [ r (n), q (n) ] henviser til det sæt beslutningsproblemer, der har verificerbare bevis med sandsynlighed, som kan tilfredsstilles i polynomet med højst r (n) tilfældige bits og ved at læse ved plus q ( n) bevisstykker. Som allerede nævnt ovenfor skal korrekte bevis altid accepteres, og forkerte bevis skal afvises med en sandsynlighed på mindst 1/2. PCP-sætningen siger, at

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

Demonstration

Et bevis på et svagere resultat, NP = PCP [n 3 , 1], gives i et af Dexter Kozens kurser.

Anvendelse til tilnærmelsesalgoritmer

PCP-sætningen har vigtige konsekvenser inden for tilnærmelsesalgoritmer . Især tjener det til at vise, at MAX-3SAT og Maximum Independent Set-problemer blandt andre ikke kan tilnærmes effektivt, medmindre P = NP .

MAX-3SAT eksempel

MAX-3SAT-problemet er som følger: givet en 3CNF-formel, dvs. i konjunktiv normal form , hvor hver klausul højst indeholder 3 liter (som i 3-SAT-problemet ), hvad er det maksimale antal klausuler, der kan opfyldes ved samme tildeling af variabler?

Resultatet af tilnærmelsesvanskeligheden er som følger:

Der er sådan en konstant , at eksistensen af ​​en tilnærmelsesalgoritme for MAX-3SAT med et tilnærmelsesforhold indebærer, at P = NP.

Dette er faktisk en følge af følgende sætning:

Der er en konstant sådan, at der for ethvert sprog eksisterer en funktion, der går fra strenge til 3CNF-formler, således at alle klausuler om kan opfyldes, og indebærer, at den tilfredsstillende klausulfraktion er mindre end .

Historie og betydning

Teoremets historie begynder i 1980 med arbejde med den bevist nul-viden om viden ( nul vidnesikker) af Goldwasser, Micali og Rackoff. Disse resultater har på forhånd intet at gøre med tilnærmelsen, men introducerer ideen om bevismester og verifikator. Forbindelsen mellem beviskontrol og tilnærmelse er lavet i begyndelsen af ​​1990'erne af Feige, Goldwasser, Lovász, Safra og Szegedy.

I 2001 modtog Sanjeev Arora , Uriel Feige , Shafi Goldwasser , Carsten Lund , László Lovász , Rajeev Motwani , Shmuel Safra , Madhu Sudan og Mario Szegedy den prestigefyldte Gödel-pris for deres papirer om PCP-sætningen ( Feige et al. 1996 ) ( Arora og Safra 1998 ) ( Arora et al. 1998 ).

I 2006 offentliggjorde Irit Dinur et helt nyt bevis på den kombinatoriske sætning, især ved hjælp af ekspanderdiagrammer ( Dinur 2007 ). Dette bevis indbragte ham 2019 Gödel-prisen .

Ingo Wegener sagde om denne sætning, at det var "det vigtigste resultat i kompleksitetsteori siden Cooks sætning  ". For Oded Goldreich er det ”kulminationen på en række imponerende værker, rig på innovationer”.

Bibliografi

Artikler

Popularisering

eksterne links

(fr) PCP-klassen i Complexity Zoo

Noter og referencer

  1. Bernard H. Korte og Jens Vygens ( overs.  Jean Fonlupt og Alexandre Skoda), kombinatorisk optimering: teori og algoritmer , Springer-Verlag ,2010( læs online ) , s.  443
  2. Init Dinurs plenarforelæsning er tilgængelig på hans personlige side på Probabilistically Checkable Proofs (survey and talk) .
  3. I vilkårene for rapporten offentliggjort i ( Ghys 2010 ).
  4. Christian Scheideler, "  Computational Models  " (adgang til 16. juli 2013 ) .
  5. (i) Dexter C. Közen , Theory of Computation , London, Springer-Verlag , al.  "Tekster inden for datalogi",2006, 119–127  s. ( ISBN  978-1-84628-297-3 , læs online )
  6. (i) Sanjeev Arora og Boaz Barak , Computational Complexity: En moderne tilgang , Cambridge University Press ,2009( ISBN  0-521-42426-7 ) , kap.  11.2.2 ("PCP og tilnærmelsesens hårdhed")
  7. Dana Moshkovitz, "  Fortællingen om PCP-sætningen  ", ACM Crossroads , bind.  18, nr .  3, 2012, s.  23-26 ( læs online )
  8. Officiel side af Gödelprisen for 2001
  9. Gödel-pris 2009-siden for zig-zag-produkt af grafer, hvis sidste afsnit vedrører beviset for Dinur
  10. "  Gödel-prisen 2019  " om EATCS (adgang til 9. august 2020 ) .
  11. "  Det vigtigste resultat i kompleksitetsteori siden Cooks sætning  " i: (en) Ingo Wegener, kompleksitetsteori: Udforskning af grænserne for effektive algoritmer , Springer,2005, 308  s. ( ISBN  978-3-540-21045-0 , læs online ) , s.  161.
  12. "  En kulmination af en række imponerende værker [...] rig 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 , læs 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;">