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