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 .
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.
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. "
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.
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 .Gyengébb eredmény, NP = PCP [n 3 , 1] bizonyítékát Dexter Kozen egyik tanfolyamán adják meg.
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 .
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 .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”.
(fr) A PCP osztály a Komplexitás Állatkertben