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] .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.
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] .
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] .
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] . .