Pravděpodobně ověřitelný důkaz - Probabilistically checkable proof
![]() | Tento článek obsahuje seznam obecných Reference, ale zůstává z velké části neověřený, protože postrádá dostatečné odpovídající vložené citace.Listopad 2012) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) ( |
v teorie výpočetní složitosti, a pravděpodobnostně ověřitelný důkaz (PCP) je typ důkaz které lze zkontrolovat pomocí randomizovaný algoritmus pomocí omezeného množství náhodnosti a čtení omezeného počtu bitů důkazu. Algoritmus je poté vyžadován k přijetí správných důkazů a odmítnutí nesprávných důkazů s velmi vysokou pravděpodobností. Standardní důkaz (nebo osvědčení ), jak se používá v ověřovatel -definovaná definice třída složitosti NP, rovněž splňuje tyto požadavky, protože kontrolní postup deterministicky přečte celý důkaz, vždy přijímá správné důkazy a nesprávné důkazy odmítá. Co je však dělá zajímavým, je existence pravděpodobnostně ověřitelných důkazů, které lze ověřit čtením pouze několika bitů důkazu pomocí náhodnosti podstatným způsobem.
Pravděpodobně ověřitelné důkazy vedou k mnoha třídám složitosti v závislosti na počtu požadovaných dotazů a použité míře náhodnosti. Třída PCP[r(n),q(n)] odkazuje na soubor rozhodovací problémy které mají pravděpodobnostně ověřitelné důkazy, které lze ověřit v polynomiálním čase maximálně r(n) náhodné bity a maximálně čtením q(n) kousky důkazu.[1] Pokud není uvedeno jinak, měly by být vždy přijaty správné důkazy a nesprávné důkazy by měly být odmítnuty s pravděpodobností větší než 1/2. The Věta o PCP, hlavní výsledek v teorii výpočetní složitosti, uvádí, že PCP[O (log n), O (1)] =NP.
Definice
Vzhledem k tomu, rozhodovací problém L(nebo jazyk L s nastavenou abecedou Σ), a pravděpodobnostně ověřitelný důkazní systém pro L s úplností C(n) a spolehlivost s(n), kde 0 ≤ s(n) ≤ C(n) ≤ 1, sestává z provera a ověřovatele. Vzhledem k požadovanému řešení x s délkou n, které by mohlo být nepravdivé, prover předloží důkaz π které státy X řeší L (X ∈ L, důkaz je řetězec ∈ ∈*). A ověřovatel je randomizovaný Oracle Turing Machine PROTI (dále jen ověřovatel), který kontroluje důkaz π za tvrzení, že X řeší L(nebo X ∈ L) a rozhodne, zda prohlášení přijme. Systém má následující vlastnosti:
- Úplnost: Pro všechny X ∈ L, po důkazu π Vyrobeno ověřovatelem systému, ověřovatel přijme prohlášení alespoň s pravděpodobností C(n),
- Zdravost: Pro všechny X ∉ L, pak pro jakýkoli důkaz π, ověřovatel omylem přijímá prohlášení s největší pravděpodobností s(n).
Pro výpočetní složitost ověřovatele máme složitost náhodnosti r(n) měřit maximální počet náhodných bitů, které PROTI používá přes všechno X délky n a složitost dotazu q(n) ověřovatele je maximální počet dotazů, které PROTI dělá π přes všechny X délky n.
Ve výše uvedené definici není délka důkazu zmíněna, protože obvykle zahrnuje abecední sadu a všechny svědky. Pro proverátora je nám jedno, jak dospívá k řešení problému; záleží nám pouze na důkazu, který poskytuje členství řešení v daném jazyce.
O ověřovateli se říká, že je neadaptivní pokud provede všechny své dotazy dříve, než obdrží jakoukoli odpověď na předchozí dotazy.
Třída složitosti PCPC(n), s(n)[r(n), q(n)] je třída všech rozhodovacích problémů, které mají pravděpodobnostně ověřitelné kontrolní systémy přes binární abecedu úplnosti C(n) a spolehlivost s(n), kde je ověřovatel neadaptivní, běží v polynomiálním čase a má složitost náhodnosti r(n) a složitost dotazu q(n).
Zkratková notace PCP[r(n), q(n)] se někdy používá pro PCP1, ½[r(n), q(n)]. Třída složitosti PCP je definován jako PCP1, ½[O (logn), O (1)].
Historie a význam
Teorie pravděpodobnostně ověřitelných důkazů studuje sílu systémů pravděpodobnostně ověřitelných důkazů za různých omezení parametrů (úplnost, spolehlivost, složitost náhodnosti, složitost dotazu a velikost abecedy). Má aplikace pro výpočetní složitost (zejména tvrdost aproximace ) a kryptografie.
Definici pravděpodobnostně ověřitelného důkazu výslovně zavedli Arora a Safra v roce 1992,[2] ačkoli jejich vlastnosti byly studovány dříve. V roce 1990 to dokázali Babai, Fortnow a Lund PCP[poly (n), poly (n)] = NEXP, poskytující první netriviální ekvivalenci mezi standardními důkazy (NEXP) a pravděpodobnostně ověřitelné důkazy.[3] The Věta o PCP prokázáno v roce 1992 to uvádí PCP[O (log n), O (1)] =NP.[2][4]
Teorie tvrdost aproximace vyžaduje podrobné pochopení role úplnosti, spolehlivosti, velikosti abecedy a složitosti dotazu v pravděpodobnostně ověřitelných důkazech.
Vlastnosti
Z hlediska výpočetní složitosti je pro extrémní nastavení parametrů definice pravděpodobnostně ověřitelných důkazů snadno považována za ekvivalentní standardní třídy složitosti. Například pro následující nastavení máme následující PCP[r (n), q (n)]:
- PCP[0, 0] = P (P je definována tak, že nemá žádnou náhodnost a nemá přístup k důkazu.)
- PCP[O (log (n)), 0] = P (Logaritmický počet náhodných bitů nepomůže polynomiálnímu Turingovu stroji, protože by mohl vyzkoušet všechny možná náhodné řetězce logaritmické délky v polynomiálním čase.)
- PCP[0, O (log (n))] = P (Bez náhodnosti lze důkaz považovat za pevný řetězec logaritmické velikosti. Stroj s polynomickým časem by mohl vyzkoušet všechny možné důkazy s logaritmickou velikostí v polynomiálním čase.)
- PCP[poly (n), 0] = coRP (Podle definice coRP.)
- PCP[0, poly (n)] = NP (Podle definice NP na základě ověřovatele.)
Věta o PCP a MIP = NEXP lze charakterizovat následovně:
- PCP[O (log n), O (1)] =NP (teorém PCP)
- PCP[poly (n), O (1)] =PCP[poly (n), poly (n)] = NEXP (MIP = NEXP).
Je také známo, že PCP[r(n), q(n)] ⊆ NTIME (poly (n, 2Ó(r(n))q(n))). Zejména, PCP[log n, poly (n)] = NP. Na druhou stranu, pokud NP ⊆ PCP[o (log n), o (log n)] pak P = NP.[2]
Lineární PCP
Lineární PCP je takový, že při daném dotazu q provede věštec na důkazu pouze lineární operaci . To znamená, že odpověď věštce na dotaz q je lineární funkcí .
Viz také
Reference
- ^ Arora, Sanjeev; Barak, Boaz (2007), Výpočetní složitost: moderní přístup, Cambridge University Press, str. 241, ISBN 978-0-521-42426-4
- ^ A b C Arora, Sanjeev; Safra, Shmuel (1998), „Pravděpodobnostní kontrola důkazů: nová charakteristika NP“, Deník ACM, 45 (1): 70–122, doi:10.1145/273865.273901
- ^ Babai, László; Fortnow, Lance; Lund, Carsten (1990), „Nedeterministický exponenciální čas má dva proverativní interaktivní protokoly“, Sborník z 31. výročního symposia o základech informatiky (FOCS 1990), s. 16–25, CiteSeerX 10.1.1.130.9311, doi:10.1109 / FSCS.1990.89520, ISBN 978-0-8186-2082-9
- ^ Arora, Sanjeev; Lund, Carsten; Motwani, Rajeev; Súdán, Madhu; Szegedy, Mario (1998), „Důkazové ověření a tvrdost problémů aproximace“, Deník ACM, 45 (3): 501–555, doi:10.1145/278298.278306
externí odkazy
- Holografický důkaz.
- Subhash Khot. Poznámky k kurzu PCP. New York University, 2008.
- Ryan O'Donnell a Venkatesan Guruswami. Poznámky k kurzu PCP a Historie věty o PCP. University of Washington, 2005.
- Složitost Zoo: PCP