PCP-tétel

A komplexitás elmélet , egy olyan területen, az elméleti számítógép-tudomány , a PCP-tétel ( betűszó az angol véletlenszerűen ellenőrizhető bizonyíték , ami lehet fordítani, franciául „  bizonyíték igazolható valószínűség  ”) egy jellemzése az osztály NP keretében egy interaktív bizonyítási rendszer . Pontosabban, az NP a döntési problémák azon osztálya , amelyek bizonyítékokkal rendelkeznek, amelyek probabilistikusan ellenőrizhetők azáltal, hogy hozzáférnek a bizonyítás állandó számához és logaritmikus számú véletlenszerű bitet használnak.

A PCP-tétel nagyon fontos az elméleti számítástechnikában: sokakat felvet az algoritmikus problémák közelítésének nehézségeiről .

Informális előadás

A PCP-tétel kimondja, hogy ha valaki tűr egy hibahatárt, akkor felesleges egy teljes bizonyítékot elolvasni , hogy meggyőződjünk annak helyességéről. Ezt az állítást a következőképpen is átfogalmazhatjuk: létezik egy állandó K, így bármely n hosszúságú matematikai P bizonyíték átírható n- ben polinomi hosszúságú P ' bizonyítékba , így elegendő csak P' K szimbólumait vizsgálni ( egy randomizált algoritmus ), hogy meg kell győzni a 99% -os pontossággal a bizonyítékokat.

"A lekvárlövés"


Az ő Plenáris előadás a 2010-es Nemzetközi Matematikai Kongresszus , Irit Dinur használt analógia közvetíteni ez a tétel. Étienne Ghys a következőképpen számolt be  :

- Mintha lenne egy szelet kenyered, amiben talán van egy kis csepp lekvár valahol, de nem tudod, hol. Véletlenszerűen vesz egy darabot a pirítósból, és nem talál lekvárt; levezetheti, hogy egyáltalán nincs lekvár? Határozottan nem, hacsak nem sok mintavételt végez. De ha azzal kezdi, hogy késsel kenje meg a lekvárt a kenyérszeleten, az mindenhol megtalálható lesz, és csak mintát kell vennie, hogy megtudja, volt-e egy csepp lekvár. Itt ugyanaz. P bizonyításból indulunk ki, amelynek valahol esetleg hibája van. Van egy módja annak, hogy „elterjesszük” a bizonyítékot egy másik P felépítéséhez , amelyben a hibák, ha vannak ilyenek, „elterjedtek” az egész helyen, és most már könnyen észlelhetők egy kis számú minta felvételével. "

PCP rendszer

Vizsgálja meg a matematikai tétel igazolásának ellenőrzésének problémáját. Mivel a bizonyítások hosszúak és nehezen ellenőrizhetőek teljes egészében, lehet keresni egy módszert a bizonyítás bemutatására oly módon, hogy elegendő annak csak egy kis részét ellenőrizni, hogy a tétel érvényességét ésszerű bizalommal meg lehessen ítélni. Diák. Ezt a kérdést valószínűségi módon ellenőrizhető bizonyítási rendszerek kezelik .

Informálisan, egy nyelv valószínűség-igazolható bizonyíték (PCP) rendszere egy polinomi időbeli valószínűség- ellenőrző , amely közvetlen hozzáféréssel rendelkezik a bináris szó egyes bitjeihez. Ez az orákulumnak nevezett szó bizonyítékot jelent, és a hitelesítő csak részben fogja megvizsgálni. Az orákulumnak feltett kérdések a bináris szó és érme dobások helyzetei, amelyek esetleg a korábbi kérdésekre adott válaszoktól függenek. A hitelesítő dönti el, hogy egy adott bejegyzés tartozik-e a nyelvhez. Ha a bejegyzés nyelvű, kérjük, hogy az ellenőr mindig fogadja el a szót, feltéve, hogy megfelelő orákulummal van ellátva. Más szavakkal, a könyvvizsgáló soha nem utasítja el azt a szót, amely a nyelvben szerepel. Ellenkező esetben, ha a szó nem szerepel a nyelvben, az ellenőr a felét meghaladó valószínűséggel elutasítja, függetlenül a használt orákulumtól.

Láthatjuk a PCP rendszereket az interaktív bizonyító rendszerek szempontjából . Ezután az orákulumot közmondásnak tekintjük (amely be akarja bizonyítani az állítást), a kérdéseket pedig annyi üzenetként, amelyet a hitelesítő küldött neki. A PCP összefüggésében úgy tekintenek, hogy a Prover nem emlékszik az előző kérdésekre, ezért válaszaiban nem veszi figyelembe a korábban feltett kérdéseket.

Érdekesebb értelmezés az, ha a PCP-rendszereket az NP-osztály hitelesítőinek általánosításaként tekintjük. Ahelyett, hogy a teljes bizonyíték kézhezvételekor polinomiális időszámítást végezne (mint például egy NP-probléma hitelesítője esetében), az ellenőrnek megengedett az érme megfordítása és a bizonyíték megvizsgálása csak az általa választott helyeken. Ez lehetővé teszi, hogy hosszú bizonyításokat vizsgáljon, legfeljebb egy bizonyos polinomszámú helyet vizsgálva, vagy ezzel egyenértékűen csak néhány bit bizonyítást.

Figyelemre méltó, hogy a PCP rendszerek lehetővé teszik a nyelvek teljes jellemzését az NP-ben . Ezt a jellemzést hasznosnak bizonyította az a kapcsolat, amely egyes NP-nehéz problémák közelítésének nehézsége, valamint a P és NP közötti egyenlőség kérdése között létrejött. Más szavakkal, a klasszikus optimalizálási problémák nem-közelítési eredményeit hozták létre az NP osztályú nyelvek PCP rendszereivel.

Államok

A valószínű bizonyítások bonyolultsági osztályokat eredményeznek a szükséges kérdések száma és az alkalmazott véletlenszerűség mértéke szerint. A PCP osztály [ r (n), q (n) ] a döntési problémák azon csoportjára utal, amelyek valószínűségével ellenőrizhető bizonyítékokkal rendelkeznek, amelyek polinomiális időben legfeljebb r (n) véletlenszerű bitekkel és plusz q ( n) a bizonyítás bitjei. Mint már fentebb említettük, a helyes igazolást mindig el kell fogadni, és a helytelen igazolást legalább 1/2 valószínűséggel el kell utasítani. A PCP tétel azt állítja

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

Demonstráció

Gyengébb eredmény, NP = PCP [n 3 , 1] bizonyítékát Dexter Kozen egyik tanfolyamán adják meg.

Alkalmazás közelítő algoritmusokra

A PCP tételnek fontos következményei vannak a közelítő algoritmusok terén . Különösen azt mutatja, hogy a MAX-3SAT és a Maximum Independent Set problémákat nem lehet hatékonyan közelíteni, hacsak P = NP .

MAX-3SAT példa

A MAX-3SAT probléma a következő: adott egy 3CNF képlet, azaz konjunktív normál alakban , amelynek mindegyik mondata legfeljebb 3 literált tartalmaz (mint a 3-SAT feladatban ), mi az a maximális számzáradék, amely kielégíthető ugyanaz a változók hozzárendelése?

A közelítési nehézség eredménye a következő:

Van egy olyan állandó, hogy a MAX-3SAT közelítési arányú közelítő algoritmusának megléte azt jelenti, hogy P = NP.

Ez tulajdonképpen a következő tétel következménye:

Van olyan konstans , hogy bármely nyelv esetében létezik olyan függvény, amely a karakterláncoktól a 3CNF képletekig megy, és amely azt jelenti, hogy a (z) összes mondata kielégíthető, és azt jelenti, hogy a kielégíthető tagmondat- értéke kisebb, mint .

Történelem és fontosság

A történelem a tétel kezdődik 1980-ban, a munka a jól bevált zéró-ismeret ismeretek ( zéró tudás bizonyítéka ) Goldwasser, Micali és Rackoff. Ezeknek az eredményeknek eleve nincs közük a közelítéshez, de bevezetik a közmondás és a hitelesítés gondolatát. A korrekció és a közelítés közötti kapcsolatot az 1990-es évek elején Feige, Goldwasser, Lovász, Safra és Szegedy hozza létre.

2001-ben Sanjeev Arora , Uriel Feige , Shafi Goldwasser , Carsten Lund , Lovász László , Rajeev Motwani , Shmuel Safra , Madhu Sudan és Mario Szegedy megkapta a rangos Gödel-díjat a PCP-tételen ( Feige et al. 1996 ) ( Arora ) írt munkáért és Safra 1998 ) ( Arora és mtsai 1998 ).

2006-ban Irit Dinur egy teljesen új bizonyítékot tett közzé a kombinatorikus tételről, nevezetesen bővítő grafikonokkal ( Dinur 2007 ). Ez a bizonyíték elnyerte neki a 2019-es Gödel-díjat .

Ingo Wegener erről a tételről azt mondta, hogy " Cook összetétele óta ez a legfontosabb eredmény a komplexitáselméletben  ". Mert Oded Goldreich , hogy „a csúcspontja a sorozat lenyűgöző alkotások, gazdag újítások”.

Bibliográfia

Cikkek

Népszerűsítés

Külső linkek

(fr) A PCP osztály a Komplexitás Állatkertben

Megjegyzések és hivatkozások

  1. Bernard H. Korte és Jens Vygens ( ford.  Jean Fonlupt és Alexandre Skoda), kombinatorikus optimalizálás: elmélet és algoritmusok , Springer-Verlag ,2010( online olvasható ) , p.  443
  2. Init Dinur plenáris előadása személyes oldalán elérhető a Probabilistically Checkable Proofs (felmérés és beszélgetés) oldalon .
  3. A ( Ghys 2010 ) -ban megjelent jelentés értelmében .
  4. Christian Scheideler, „  Számítási modellek  ” (hozzáférés : 2013. július 16. ) .
  5. (a) Dexter C. Kozen , Theory of számítása , London, Springer-Verlag , al.  "Szövegek a számítástechnikában",2006, 119–127  . ( ISBN  978-1-84628-297-3 , online olvasás )
  6. (in) Sanjeev Arora és Boaz Barak , számítási komplexitás: A Modern Approach , Cambridge University Press ,2009( ISBN  0-521-42426-7 ) , fej .  11.2.2 ("PCP és a közelítés keménysége")
  7. Dana Moshkovitz, „  A PCP-tétel meséje  ”, ACM Crossroads , vol.  18, n o  3, 2012, P.  23–26 ( online olvasás )
  8. A 2001. évi Gödel-díj hivatalos oldala
  9. Gödel-díj 2009 oldal, a grafikonok cikk-cakk termékéért, amelynek utolsó bekezdése a Dinur igazolására vonatkozik
  10. "  2019 Gödel Prize  " , az EATCS-en (hozzáférés : 2020. augusztus 9. ) .
  11. "  A komplexitáselmélet legfontosabb eredménye Cook tétele óta  ": (en) Ingo Wegener, Komplexitáselmélet: A hatékony algoritmusok határainak feltárása , Springer,2005, 308  p. ( ISBN  978-3-540-21045-0 , online olvasás ) , p.  161.
  12. "  Az innovatív ötletekben gazdag, lenyűgöző művek sorozatának csúcspontja  ": (en) Oded Goldreich, Computational Complexity: A Conceptual Perspective , Cambridge, Cambridge University Press ,2008, 606  p. ( ISBN  978-0-521-88473-0 , online olvasás ) , p.  405.
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">