PCP-sætning

I beregningskompleksitetsteori angiver PCP-sætningen ( probabilistisk kontrollerbare  beviser  - sandsynligt verificerbare beviser), at enhver løsning på et beslutningsproblem i NP -kompleksitetsklassen har et sandsynligt verificerbart bevis (et bevis, der kan verificeres ved hjælp af en randomiseret algoritme ) af konstant forespørgselskompleksitet og logaritmisk kompleksitet af tilfældighed (bruger logaritmisk antal tilfældige bits).

PCP-sætningen er hjørnestenen i tilnærmelsesberegningskompleksitetsteori , som udforsker den iboende kompleksitet i at udvikle effektive tilnærmelsesalgoritmer til forskellige optimeringsproblemer . Sætningen er noteret af Ingo Wegener som "det vigtigste resultat i kompleksitetsteori siden Cooks sætning " [1] og af Oded Goldreich som "kulminationen af ​​en kæde af imponerende værker […] rig på nye ideer" " [2] .

Der er også kritik. Så i Boss' bog [3] siges det: "På et tidspunkt gav det et plask. Snebolden af ​​publikationer vokser stadig ... Den nye, i det væsentlige, definition af NP-klassen kaster yderligere lys, men uden de store konsekvenser. … Hvad angår selve PCP-systemet, er det i det væsentlige afhængigt af det magiske Oracle, og frigiver derfor ikke ligheden NP = PCP [O(log n ), O(1)] til det praktiske plan."

PCP-sætningen siger det

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

PCP og tilnærmelseskompleksitet

En alternativ formulering af PCP-sætningen siger, at søgningen efter den maksimale andel af opfyldte betingelser i begrænsningsproblemet er NP-svær for tilnærmelse med en konstant koefficient.

Formelt for nogle konstante K og α < 1 er problemet ( L ja , L nej ) et NP-hårdt beslutningsproblem:

Her er Φ problemet med at opfylde begrænsningsbetingelserne over et boolsk alfabet med højst K variabler pr. konstant [5]

Som en konsekvens af denne teorem kan det påvises, at løsninger på mange optimeringsproblemer, herunder at finde den maksimale tilfredsstillelse af booleske formler , det maksimale uafhængige sæt i en graf og den korteste gittervektor , ikke kan tilnærmes effektivt, medmindre P = NP er opfyldt .

Disse resultater kaldes nogle gange også PCP-sætninger, fordi de kan ses som sandsynligt verificerbare beviser for NP-problemer med nogle yderligere strukturer.

Historie

PCP-sætningen er kulminationen på en lang rejse i udviklingen af beviser og sandsynligt verificerbare beviser.

Den første sætning, der forbinder almindelige beviser og sandsynligt verificerbare beviser, erklærede det , og blev bevist i bogen fra 1990 [6] .

Historie siden det første bevis på sætningen i 1990

Senere blev metoden brugt i denne artikel udvidet i artiklen af ​​Babai, Fortnov, Levin, Shegedi (1991) [7] , samt i artiklerne af Feige, Goldwasser, Lund, Shegedi (1991) og Arora og Safra (1992) [8] , som gav et bevis for PCP-sætningen i et papir fra 1992 af Arora, Lund, Motwani, Sudan og Shegedi [9] . I 2001 blev Gödel-prisen tildelt Sanjeev Arora , Uriel Feiga , Shafi Goldwasser , Karsten Lund Laszlo Lovas , Rajiv Motwani , Shmuel Safra , Sudan og Szegedi for deres arbejde med PCP-sætningen og dens

I 2005 opdagede Irit Dinur endnu et bevis på PCP-sætningen ved hjælp af ekspandere [5] .

Kvanteanalog af PCP-sætningen

I 2012 publicerede Thomas Vidick og Tsuyoshi Ito en artikel [10] der viser "den alvorlige begrænsning af komplekse samordningstjek i et multiplayer-spil". Dette er et vigtigt skridt fremad i at bevise en kvanteanalog af PCP-sætningen [11] , og professor Dorit Aharonov kaldte den "en kvanteanalog af en tidligere artikel om interaktive tests", som "i det væsentlige førte til PCP-sætningen" [12] .

Noter

  1. ↑ Ingo Wegener. Nondeterministisk eksponentiel tid har interaktive protokoller med to beviser // Complexity Theory: Exploring the Limits of Efficient Algorithms . - Springer, 2005. - ISBN 978-3-540-21045-0 .
  2. ↑ Oded Goldreich. Beregningsmæssig kompleksitet: Et konceptuelt perspektiv . - Cambridge University Press, 2008. - ISBN 978-0-521-88473-0 . Arkiveret 13. april 2014 på Wayback Machine
  3. ↑ 1 2 Boss V. Brute Force og effektive algoritmer: Studievejledning. - M .: Forlaget LKI, 2008. - T. 10. - (Forelæsninger om matematik). - ISBN 978-5-382-00642-0 .
  4. ↑ Jose Falcon, Mitesh Jain. En introduktion til probabilistisk kontrollerbare beviser og PCP-sætningen . - 2013. - S. 3 . Arkiveret fra originalen den 14. februar 2019.
  5. ↑ 1 2 Irit Dinur. PCP-sætningen ved gap amplification // Journal of the ACM. - 2007. - T. 54 , no. 3 . - S. 70-122 . - doi : 10.1145/1236457.1236459 .
  6. ↑ Lászlo Babai, Lance Fortnow, Carsten Lund. Ikke-deterministisk eksponentiel tid har interaktive protokoller med to beviser // 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. Kontrol af beregninger i polylogaritmisk tid // STOC '91: Proceedings of the 23th annual ACM symposium on Theory of computing. - ACM, 1991. - S. 21-32. - ISBN 978-0-89791-397-3 .
  8. ↑ Sanjeev Arora, Shmuel Safra. Probabilistisk kontrol af beviser: En ny karakterisering af NP // Journal of the ACM. - 1998. - T. 45 , no. 1 . - S. 70-122 . - doi : 10.1145/273865.273901 .
  9. ↑ Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy. Bevisverifikation og hårdheden af ​​tilnærmelsesproblemer // Journal of the ACM. - 1998. - T. 45 , no. 3 . - S. 501-555 . - doi : 10.1145/278298.278306 .
  10. ↑ Ito, Tsuyoshi; Vidick, Thomas Et interaktivt bevis med flere beviser for NEXP-lyd mod indviklede provere .
  11. ↑ Hardesty, Larry MIT News Release: 10-årigt problem inden for teoretisk datalogi falder . MIT News Office (30. juli 2012). "Interaktive kontroller er grundlaget for kryptografiske systemer og er nu meget udbredt, men for dataloger er de kun et vigtigt middel til at trænge ind i essensen af ​​beregningsmæssige kompleksitetsproblemer." Hentet 10. august 2012. Arkiveret fra originalen 10. august 2012.
  12. ↑ Hardesty, Larry 10-årig problem i teoretisk datalogi falder . MIT News Office (31. juli 2012). "Dorit Aharonov, en professor ved det hebraiske universitet i Jerusalem, sagde, at Vidick og Itos papir er en kvanteanalog af et tidligere papir om interaktive beviser, som "i det væsentlige førte til PCP-sætningen, og selve PCP-sætningen er uden tvivl vigtigste resultat inden for kompleksitetsteori i de sidste 20 år." Han sagde også, at det nye papir "ser ud til at være et vigtigt skridt fremad i at bevise kvanteanalogen til PCP-sætningen, som nu er det vigtigste åbne spørgsmål inden for kvanteberegningskompleksitetsteori." Hentet 10. august 2012. Arkiveret fra originalen 9. august 2012.

Litteratur