PCP-lause

Laskennallisen monimutkaisuuden teoriassa PCP-lause ( todennäköisesti tarkistettavissa olevat  todisteet  - todennäköisyydellä varmennettavissa oleva todistus) sanoo, että jokaisella ratkaisuongelman ratkaisulla NP - kompleksisuusluokassa on todennäköisyydellä todennettavissa oleva todistus (todistus, joka voidaan varmistaa satunnaistetulla algoritmilla ) . vakiokyselyn monimutkaisuus ja satunnaisuuden logaritminen monimutkaisuus (käyttää logaritmista satunnaisten bittien määrää).

PCP-lause on approksimaatiolaskennallisen monimutkaisuusteorian kulmakivi , joka tutkii luontaista monimutkaisuutta kehitettäessä tehokkaita approksimaatioalgoritmeja erilaisiin optimointiongelmiin . Ingo Wegener mainitsee lauseen " monimutkaisuusteorian tärkeimmäksi tulokseksi Cookin lauseen jälkeen " [1] ja Oded Goldreich "vaikuttavien teosten ketjun huipentumaksi, joka sisältää runsaasti uusia ideoita. " [2] .

On myös kritiikkiä. Joten Bossin kirjassa [3] sanotaan: ”Kerran se teki roiskeen. Julkaisujen lumipallo kasvaa edelleen... Uusi, pohjimmiltaan NP-luokan määritelmä valaisee lisävalaistusta, mutta ilman suuria seurauksia. … Mitä tulee itse PCP-järjestelmään, se luottaa olennaisesti maagiseen Orakkeliin, eikä siksi vapauta yhtälöä NP = PCP [O(log n ), O(1)] käytännön tasolle.”

PCP-lause sanoo sen

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

PCP ja approksimaatio monimutkaisuus

Vaihtoehtoinen PCP-lauseen muotoilu väittää, että rajoitusongelman täyttyneiden ehtojen maksimiosuuden etsiminen on NP-kovaa approksimaatiolle vakiokertoimella.

Muodollisesti joillekin vakioille K ja α < 1 ongelma ( L kyllä ​​, L ei ) on NP-kova päätösongelma:

Tässä Φ on ongelma rajoitusehtojen täyttymisestä Boolen aakkostossa, jossa on enintään K muuttujaa vakiota kohti [5]

Tämän lauseen seurauksena voidaan osoittaa, että ratkaisuja moniin optimointiongelmiin, mukaan lukien Boolen kaavojen maksimitäytettävyyden löytäminen , graafin suurin riippumaton joukko ja lyhin hilavektori , ei voida tehokkaasti approksimoida, ellei P = NP on tyytyväinen .

Näitä tuloksia kutsutaan joskus myös PCP-lauseiksi, koska niitä voidaan pitää todennäköisyydellä todennettavissa olevina todisteina NP-ongelmista joidenkin lisärakenteiden kanssa.

Historia

PCP-lause on pitkän matkan huipentuma todisteiden ja todennäköisyydellä todennettavien todisteiden kehittämisessä.

Ensimmäinen lause, joka yhdistää tavalliset todisteet ja todennäköisyydellä todennettavat todisteet, totesi, että , ja se todistettiin vuoden 1990 kirjassa [6] .

Historiaa lauseen ensimmäisestä todistuksesta vuonna 1990

Myöhemmin tässä artikkelissa käytettyä menetelmää laajennettiin Babain, Fortnovin, Levinin, Shegedin (1991) [7] artikkelissa sekä Feigen, Goldwasserin, Lundin, Shegedin (1991) sekä Aroran ja Safran artikkeleissa. (1992) [8] , joka osoitti PCP-lauseen Aroran, Lundin, Motwanin, Sudanin ja Shegedin vuoden 1992 artikkelissa [9] . Vuonna 2001 Gödel-palkinto myönnettiin Sanjeev Aroralle , Uriel Feigalle , Shafi Goldwasserille , Karsten Lundille Laszlo Lovasille , Rajiv Motwanille , Shmuel Safralle , Sudanille ja Szegedille heidän työstään PCP-lauseen parissa ja sen

Vuonna 2005 Irit Dinur löysi toisen todisteen PCP-lauseesta käyttämällä laajentajia [5] .

PCP-lauseen kvanttianalogi

Vuonna 2012 Thomas Vidick ja Tsuyoshi Ito julkaisivat artikkelin [10] , joka osoitti "moninpelin monimutkaisten salaliittotarkistusten vakavan rajoituksen". Tämä on tärkeä askel eteenpäin PCP-lauseen kvantianalogin todistamisessa [11] , ja professori Dorit Aharonov kutsui sitä "kvanttianalogiksi aikaisemmasta interaktiivisia testejä käsittelevästä artikkelista", joka "johti olennaisesti PCP-lauseeseen" [12] . .

Muistiinpanot

  1. Ingo Wegener. Epädeterministisellä eksponentiaalisella ajalla on kaksi todistettavaa interaktiivista protokollaa // Kompleksisuusteoria: Tehokkaiden algoritmien rajojen tutkiminen . - Springer, 2005. - ISBN 978-3-540-21045-0 .
  2. Oded Goldreich. Laskennallinen monimutkaisuus: käsitteellinen näkökulma . - Cambridge University Press, 2008. - ISBN 978-0-521-88473-0 . Arkistoitu 13. huhtikuuta 2014 Wayback Machineen
  3. 1 2 Boss V. Raaka voima ja tehokkaat algoritmit: Opinto-opas. - M .: Kustantaja LKI, 2008. - T. 10. - (Matematiikan luentoja). - ISBN 978-5-382-00642-0 .
  4. Jose Falcon, Mitesh Jain. Johdatus todennäköisyydellä tarkistettaviin todisteisiin ja PCP-lauseeseen . - 2013. - S. 3 . Arkistoitu alkuperäisestä 14. helmikuuta 2019.
  5. 1 2 Irit Dinur. PCP-lause aukon vahvistuksella // 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. Epädeterministisellä eksponentiaalisella ajalla on kaksi todistettua interaktiivista protokollaa // 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. Laskentatoimien tarkistus polylogaritmisessa ajassa // STOC '91: Proceedings of the 23th century ACM symposium on Theory of Computing. - ACM, 1991. - s. 21-32. - ISBN 978-0-89791-397-3 .
  8. Sanjeev Arora, Shmuel Safra. Todistusten todennäköisyystarkistus: NP:n uusi karakterisointi // 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. Todistuksen todentaminen ja approksimaatioongelmien kovuus // Journal of the ACM. - 1998. - T. 45 , no. 3 . - S. 501-555 . - doi : 10.1145/278298.278306 .
  10. Ito, Tsuyoshi; Vidick, Thomas Interaktiivinen monitodistaja NEXP-äänelle sotkeutuneita ääniä vastaan .
  11. Hardesty, Larry MIT News Release: 10 vuotta vanha ongelma teoreettisessa tietotekniikassa kaatuu . MIT News Office (30. heinäkuuta 2012). "Vuorovaikutteiset tarkistukset ovat salausjärjestelmien perusta, ja niitä käytetään nykyään laajalti, mutta tietojenkäsittelytieteilijöille ne ovat vain tärkeä keino tunkeutua laskennallisten monimutkaisuusongelmien ytimeen." Haettu 10. elokuuta 2012. Arkistoitu alkuperäisestä 10. elokuuta 2012.
  12. Hardesty, Larry 10-vuotias teoreettisen tietojenkäsittelytieteen ongelma kaatuu . MIT News Office (31. heinäkuuta 2012). "Jerusalemin heprealaisen yliopiston professori Dorit Aharonov sanoi, että Vidickin ja Iton paperi on kvanttianalogi aikaisemmalle interaktiivisia todisteita käsittelevälle paperille, joka "johti olennaisesti PCP-lauseeseen, ja itse PCP-lause on epäilemättä monimutkaisuusteorian tärkein tulos viimeisen 20 vuoden aikana." Hän sanoi myös, että uusi paperi "näyttää olevan tärkeä askel eteenpäin PCP-lauseen kvanttianalogin todistamisessa, mikä on nyt tärkein avoin kysymys kvanttilaskennan monimutkaisuusteoriassa". Haettu 10. elokuuta 2012. Arkistoitu alkuperäisestä 9. elokuuta 2012.

Kirjallisuus