PCP-sats

I beräkningskomplexitetsteorin anger PCP-satsen ( probabilistiskt kontrollerbara  bevis  - probabilistiskt verifierbara bevis) att varje lösning på ett beslutsproblem i NP -komplexitetsklassen har ett sannolikhetskontrollerbart bevis (ett bevis som kan verifieras med en randomiserad algoritm ) av konstant frågekomplexitet och logaritmisk komplexitet av slumpmässighet (använder logaritmiskt antal slumpmässiga bitar).

PCP-satsen är hörnstenen i approximationsberäkningskomplexitetsteorin , som utforskar den inneboende komplexiteten i att utveckla effektiva approximationsalgoritmer för olika optimeringsproblem . Teoremet noteras av Ingo Wegener som "det viktigaste resultatet i komplexitetsteorin sedan Cooks teorem " [1] och av Oded Goldreich som "kulmen av en kedja av imponerande verk […] rika på nya idéer" " [2] .

Det finns också kritik. Så i boken av Boss [3] sägs det: "En gång gjorde det ett stänk. Snöbollen av publikationer växer fortfarande ... Den nya, i huvudsak, definitionen av NP-klassen kastar ytterligare ljus, men utan större konsekvenser. … När det gäller själva PCP-systemet, förlitar det sig i huvudsak på det magiska Oracle, och släpper därför inte ut jämställdheten NP = PCP [O(log n ), O(1)] till det praktiska planet.”

PCP-satsen säger det

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

PCP och approximationskomplexitet

En alternativ formulering av PCP-satsen säger att sökandet efter den maximala andelen tillfredsställda villkor i begränsningsproblemet är NP-svårt för approximation med en konstant koefficient.

Formellt, för vissa konstanter K och α < 1, är problemet ( L ja , L nej ) ett NP-hårt beslutsproblem:

Här är Φ problemet med att uppfylla begränsningsvillkoren över ett booleskt alfabet med högst K variabler per konstant [5]

Som en konsekvens av detta teorem kan det visas att lösningar på många optimeringsproblem, inklusive att hitta den maximala tillfredsställelsen av booleska formler , den maximala oberoende mängden i en graf och den kortaste gittervektorn , inte kan approximeras effektivt om inte P = NP är uppfylld .

Dessa resultat kallas ibland även för PCP-satser eftersom de kan ses som sannolikhet verifierbara bevis på NP-problem med några ytterligare strukturer.

Historik

PCP-satsen är kulmen på en lång resa i utvecklingen av bevis och probabilistiskt verifierbara bevis.

Den första satsen, som förenade vanliga bevis och probabilistiskt verifierbara bevis, påstod att , och bevisades i 1990 års bok [6] .

Historia sedan det första beviset för satsen 1990

Senare har metoden som används i denna artikel utökats i artikeln av Babai, Fortnov, Levin, Shegedi (1991) [7] , samt i artiklarna av Feige, Goldwasser, Lund, Shegedi (1991) och Arora och Safra (1992) [8] , som gav ett bevis på PCP-satsen i en artikel från 1992 av Arora, Lund, Motwani, Sudan och Shegedi [9] . År 2001 delades Gödelpriset ut till Sanjeev Arora , Uriel Feiga , Shafi Goldwasser , Karsten Lund Laszlo Lovas , Rajiv Motwani , Shmuel Safra , Sudan och Szegedi för deras arbete med PCP-satsen och dess

År 2005 upptäckte Irit Dinur ytterligare ett bevis på PCP-satsen med hjälp av expanderare [5] .

Kvantanalog till PCP-satsen

2012 publicerade Thomas Vidick och Tsuyoshi Ito en artikel [10] som visar "den allvarliga begränsningen av komplexa maskopikontroller i ett multiplayer-spel". Detta är ett viktigt steg framåt för att bevisa en kvantanalog av PCP-satsen [11] , och professor Dorit Aharonov kallade den "en kvantanalog av en tidigare uppsats om interaktiva tester", som "i huvudsak ledde till PCP-satsen" [12] .

Anteckningar

  1. ↑ Ingo Wegener. Icketerministisk exponentiell tid har interaktiva protokoll med två bevis // Complexity Theory: Exploring the Limits of Efficient Algorithms . - Springer, 2005. - ISBN 978-3-540-21045-0 .
  2. ↑ Oded Goldreich. Beräkningskomplexitet: ett konceptuellt perspektiv . - Cambridge University Press, 2008. - ISBN 978-0-521-88473-0 . Arkiverad 13 april 2014 på Wayback Machine
  3. ↑ 1 2 Boss V. Brute Force och effektiva algoritmer: Studieguide. - M .: Förlag LKI, 2008. - T. 10. - (Föreläsningar om matematik). - ISBN 978-5-382-00642-0 .
  4. ↑ Jose Falcon, Mitesh Jain. En introduktion till probabilistiskt kontrollerbara bevis och PCP-satsen . - 2013. - S. 3 . Arkiverad från originalet den 14 februari 2019.
  5. ↑ 1 2 Irit Dinur. PCP-satsen genom gapförstärkning // Journal of the ACM. - 2007. - T. 54 , nr. 3 . - S. 70-122 . - doi : 10.1145/1236457.1236459 .
  6. ↑ Lászlo Babai, Lance Fortnow, Carsten Lund. Icketerministisk exponentiell tid har interaktiva protokoll med två bevis // 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. ↑ László Babai, Lance Fortnow, Leonid Levin, Mario Szegedy. Kontroll av beräkningar i polylogaritmisk tid // STOC '91: Proceedings of the twenty-thirth annual ACM symposium on Theory of computing. - ACM, 1991. - S. 21-32. - ISBN 978-0-89791-397-3 .
  8. ↑ Sanjeev Arora, Shmuel Safra. Probabilistisk kontroll av bevis: En ny karakterisering av NP // Journal of the ACM. - 1998. - T. 45 , nr. 1 . - S. 70-122 . - doi : 10.1145/273865.273901 .
  9. ↑ Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy. Bevisverifiering och hårdheten hos approximationsproblem // Journal of the ACM. - 1998. - T. 45 , nr. 3 . - S. 501-555 . - doi : 10.1145/278298.278306 .
  10. ↑ Ito, Tsuyoshi; Vidick, Thomas Ett interaktivt bevis för NEXP-ljud mot intrasslade provare .
  11. ↑ Hardesty, Larry MIT News Release: 10-åriga problem i teoretisk datavetenskap faller . MIT News Office (30 juli 2012). "Interaktiva kontroller är grunden för kryptografiska system och används nu flitigt, men för datavetare är de bara ett viktigt sätt att penetrera kärnan i beräkningskomplexitetsproblem." Hämtad 10 augusti 2012. Arkiverad från originalet 10 augusti 2012.
  12. ↑ Hardesty, Larry 10-åriga problem i teoretisk datavetenskap faller . MIT News Office (31 juli 2012). "Dorit Aharonov, professor vid hebreiska universitetet i Jerusalem, sa att Vidick och Itos uppsats är en kvantanalog till en tidigare uppsats om interaktiva bevis, som "i huvudsak ledde till PCP-satsen, och i sig är PCP-satsen utan tvekan det viktigaste resultatet inom komplexitetsteorin under de senaste 20 åren." Han sa också att det nya dokumentet "tycks vara ett viktigt steg framåt för att bevisa kvantanalogen till PCP-teoremet, som nu är den största öppna frågan inom kvantberäkningskomplexitetsteorin." Hämtad 10 augusti 2012. Arkiverad från originalet 9 augusti 2012.

Litteratur