PCP tétel

A számítási komplexitáselméletben a PCP tétel ( valószínűleg ellenőrizhető  bizonyítékok  - valószínűségileg ellenőrizhető bizonyítás) kimondja, hogy az NP komplexitási osztályban lévő döntési probléma bármely megoldása rendelkezik valószínűségileg ellenőrizhető bizonyítással (egy véletlenszerű algoritmussal ellenőrizhető bizonyítással ). állandó lekérdezési összetettség és a véletlenszerűség logaritmikus összetettsége (a véletlen bitek logaritmikus számát használja).

A PCP-tétel a közelítő számítási komplexitáselmélet sarokköve, amely feltárja a különféle optimalizálási problémák hatékony közelítő algoritmusainak kifejlesztésében rejlő komplexitást . A tételt Ingo Wegener „a komplexitáselmélet legfontosabb eredményeként Cook-tétel óta ” [1] , Oded Goldreich pedig „a lenyűgöző művek […] új ötletekben gazdag láncolatának csúcspontjaként” jegyzi meg. " [2] .

Kritika is van. Tehát a Boss [3] könyvében ez áll: „Egy időben ez feltűnést keltett. A kiadványok hógolyója még mindig nő... Az NP-osztály új, lényegében definíciója további fényt vet, de különösebb következmények nélkül. […] Ami magát a PCP-rendszert illeti, az alapvetően a varázslatos Oracle-re támaszkodik, és ezért nem engedi ki az NP = PCP [O(log n ), O(1)] egyenlőséget a gyakorlati síkra.”

A PCP tétel azt mondja ki

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

PCP és közelítés bonyolultsága

A PCP-tétel egy alternatív megfogalmazása szerint az kényszerproblémában a teljesült feltételek maximális arányának keresése NP-nehéz konstans együtthatóval való közelítéshez.

Formálisan valamilyen K állandó és α < 1 esetén a probléma ( L igen , L nem ) egy NP-nehéz döntési probléma:

Itt Φ a kényszerfeltételek teljesítésének problémája egy Boole-ábécében, állandónként legfeljebb K változóval [5]

Ennek a tételnek a következményeként kimutatható, hogy számos optimalizálási probléma megoldása, beleértve a logikai képletek maximális kielégíthetőségének megtalálását , a gráfban a maximális független halmazt és a legrövidebb rácsvektort , nem közelíthető hatékonyan, hacsak nem P. = NP teljesül .

Ezeket az eredményeket néha PCP-tételeknek is nevezik, mivel néhány további struktúrával az NP-problémák valószínűségileg igazolható bizonyítékainak tekinthetők.

Történelem

bizonyítások és a valószínűségileg igazolható bizonyítások fejlesztésében tett hosszú utazás csúcspontja .

Az első tétel, amely a közönséges bizonyításokat és a valószínűségileg ellenőrizhető bizonyításokat kapcsolta össze, kimondta, hogy , és az 1990-es könyvben [6] igazolták .

Történelem a tétel 1990-es első bizonyítása óta

Később az ebben a cikkben alkalmazott módszert Babai, Fortnov, Levin, Shegedi (1991) [7] , valamint Feige, Goldwasser, Lund, Shegedi (1991), valamint Arora és Safra cikkeiben bővítették ki. (1992) [8] , amely Arora, Lund, Motwani, Sudan és Shegedi 1992-es cikkében [9] bizonyítja a PCP-tételt . 2001-ben a Gödel-díjat Sanjeev Arora , Uriel Feiga , Shafi Goldwasser , Karsten Lund Lovas László , Rajiv Motwani , Shmuel Safra , Sudan és Szegedi kapta a PCP-tételen és annak

2005-ben Irit Dinur fedezte fel a PCP-tétel újabb bizonyítását kiterjesztők segítségével [5] .

A PCP-tétel kvantumanalógja

2012-ben Thomas Vidick és Tsuyoshi Ito publikált egy cikket [10] , amely bemutatja "az összetett összejátszások ellenőrzésének szigorú korlátozását egy többszereplős játékokban". Ez egy fontos előrelépés a PCP-tétel kvantumanalógjának bizonyítása terén [11] , és Dorit Aharonov professzor "egy korábbi interaktív tesztekről szóló tanulmány kvantumanalógjának" nevezte, ami "lényegében a PCP-tételhez vezetett" [12]. .

Jegyzetek

  1. ↑ Ingo Wegener. A nemdeterminisztikus exponenciális időnek két próbája van az interaktív protokolloknak // Komplexitáselmélet: A hatékony algoritmusok határainak feltárása . - Springer, 2005. - ISBN 978-3-540-21045-0 .
  2. ↑ Oded Goldreich. Számítási komplexitás: fogalmi perspektíva . - Cambridge University Press, 2008. - ISBN 978-0-521-88473-0 . Archiválva : 2014. április 13. a Wayback Machine -nél
  3. ↑ 1 2 Boss V. Brute Force and Efficient Algorithms: Study Guide. - M .: LKI Kiadó, 2008. - T. 10. - (Matematikai előadások). - ISBN 978-5-382-00642-0 .
  4. ↑ Jose Falcon, Mitesh Jain. Bevezetés a valószínűségileg ellenőrizhető bizonyításokba és a PCP-tételbe . - 2013. - S. 3 . Archiválva az eredetiből 2019. február 14-én.
  5. ↑ 1 2 Irit Dinur. A PCP tétel réserősítéssel // Journal of the ACM. - 2007. - T. 54 , sz. 3 . - S. 70-122 . - doi : 10.1145/1236457.1236459 .
  6. ↑ Babai László, Lance Fortnow, Carsten Lund. A nemdeterminisztikus exponenciális időnek két bevált interaktív protokollja van // SFCS '90: Proceedings of the 31st Annual Symposium on Foundations of Computer Science. - IEEE Computer Society, 1990. - S. 16-25. - ISBN 978-0-8186-2082-9 .
  7. ↑ Babai László, Lance Fortnow, Leonid Levin, Mario Szegedy. Számítások ellenőrzése polilogaritmikus időben // STOC '91: Proceedings of the huszonharmadik éves ACM szimpózium a számítástudomány elméletéről. - ACM, 1991. - P. 21-32. - ISBN 978-0-89791-397-3 .
  8. ↑ Sanjeev Arora, Shmuel Safra. Bizonyítások valószínűségi ellenőrzése: Az NP új jellemzése // Journal of the ACM. - 1998. - T. 45 , sz. 1 . - S. 70-122 . - doi : 10.1145/273865.273901 .
  9. ↑ Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy. Bizonyítási ellenőrzés és a közelítési problémák keménysége // Journal of the ACM. - 1998. - T. 45 , sz. 3 . - S. 501-555 . - doi : 10.1145/278298.278306 .
  10. ↑ Ito, Tsuyoshi; Vidick, Thomas Többpróbálós interaktív bizonyíték a NEXP hanghoz a belegabalyodott hangszórók ellen .
  11. ↑ Hardesty, Larry MIT hírközlemény: 10 éves probléma az elméleti számítástechnikában bukott . MIT News Office (2012. július 30.). „Az interaktív ellenőrzések a kriptográfiai rendszerek alapját képezik, és ma már széles körben használatosak, de az informatikusok számára csak a számítási komplexitási problémák lényegébe való behatolás fontos eszközei.” Letöltve: 2012. augusztus 10. Az eredetiből archiválva : 2012. augusztus 10..
  12. ↑ Hardesty, Larry 10 éves probléma az elméleti számítástechnikában bukik . MIT News Office (2012. július 31.). Dorit Aharonov, a Jeruzsálemi Héber Egyetem professzora azt mondta, hogy Vidick és Ito írása kvantumanalógja egy korábbi interaktív bizonyítással foglalkozó tanulmánynak, amely „lényegében a PCP-tételhez vezetett, és maga A PCP-tétel kétségtelenül a A komplexitáselmélet legfontosabb eredménye az elmúlt 20 évben.” Azt is elmondta, hogy az új tanulmány „fontos előrelépésnek tűnik a PCP-tétel kvantumanalógjának bizonyítása felé, amely jelenleg a kvantumszámítási komplexitáselmélet fő nyitott kérdése”. Letöltve: 2012. augusztus 10. Az eredetiből archiválva : 2012. augusztus 9..

Irodalom