Protokol Arthur – Merlin - Arthur–Merlin protocol
![]() | tento článek potřebuje další citace pro ověření.Červenec 2016) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) ( |
v teorie výpočetní složitosti, an Protokol Arthur – Merlin je interaktivní kontrolní systém ve kterém jsou hody mincí ověřovatele omezeny na veřejnost (tj. jsou známy i proverovi). Tuto představu představil Babai (1985). Goldwasser & Sipser (1986) dokázal, že vše (formální) jazyky s interaktivními důkazy libovolné délky se soukromými mincemi mají také interaktivní důkazy s veřejnými mincemi.
Vzhledem k tomu, že dva účastníci protokolu nazvali Arthur a Merlin, je základním předpokladem to, že Arthur je standardní počítač (nebo ověřovatel) vybavený zařízení generující náhodné číslo, zatímco Merlin je ve skutečnosti věštec s nekonečnou výpočetní silou (také známou jako prover); ale Merlin není nutně upřímný, takže Arthur musí analyzovat informace poskytnuté Merlinem v reakci na Arthurovy dotazy a sám rozhodnout o problému. Tento protokol považuje tento problém za řešitelný, pokud má Merlin vždy, když je odpověď „ano“, několik sérií odpovědí, které způsobí, že Arthur přijme alespoň2⁄3 času, a pokud je odpověď „ne“, Arthur nikdy nepřijme více než1⁄3 času. Arthur tedy funguje jako pravděpodobnostní ověřovatel polynomiálního času, za předpokladu, že mu je přidělen polynomiální čas pro jeho rozhodování a dotazy.
MA
Nejjednodušší takový protokol je protokol s 1 zprávou, kde Merlin pošle Arturovi zprávu, a poté se Arthur rozhodne, zda to přijme, nebo ne spuštěním pravděpodobnostního polynomiálního výpočtu času. (Je to podobné jako definice NP na základě ověřovatele, jediný rozdíl je v tom, že Arthur zde může používat náhodnost.) Merlin nemá v tomto protokolu přístup k Arthurovým hodům mincí, protože se jedná o protokol s jednou zprávou a Arthur hodí své mince až poté, co obdrží Merlinovu zprávu. Tento protokol se nazývá MA. Neformálně, a Jazyk L je v MA pokud pro všechny řetězce v jazyce existuje důkaz polynomiální velikosti, že Merlin může poslat Artura, aby ho o této skutečnosti přesvědčil s vysokou pravděpodobností, a pro všechny řetězce, které nejsou v jazyce, neexistuje žádný důkaz, který by Artura přesvědčil s vysokou pravděpodobností.
Formálně třída složitosti MA je sada rozhodovacích problémů, o nichž lze v polynomiálním čase rozhodnout protokolem Arthur – Merlin, kde jediný Merlinův pohyb předchází jakýkoli výpočet provedený Arthurem. Jinými slovy jazyk L je v MA pokud existuje polynomiálně-časově deterministický Turingův stroj M a polynomy p, q tak, že pro každý vstupní řetězec X délky n = |X|,
- -li X je v L, pak
- -li X není v L, pak
Druhou podmínku lze alternativně zapsat jako
- -li X není v L, pak
Abychom to porovnali s výše uvedenou neformální definicí, z je údajný důkaz od Merlina (jehož velikost je ohraničena polynomem) a y je náhodný řetězec, který používá Arthur a který je také polynomiálně ohraničený.
DOPOLEDNE
The třída složitosti DOPOLEDNE (nebo Dopoledne [2]) je sada rozhodovací problémy o tom může v polynomiálním čase rozhodnout protokol Arthur – Merlin se dvěma zprávami. Existuje pouze jeden pár dotaz / odpověď: Arthur hodí nějaké náhodné mince a odešle výsledek Všechno Když jeho mince hodí Merlinovi, Merlin odpoví domnělým důkazem a Arthur důkaz deterministicky ověří. V tomto protokolu může Arthur pouze posílat výsledky losování mincí Merlinovi a v závěrečné fázi se musí Arthur rozhodnout, zda přijme nebo odmítne, pouze pomocí svých dříve vygenerovaných náhodných mincí a Merlinovy zprávy.
Jinými slovy jazyk L je v DOPOLEDNE pokud existuje polynomiálně-časově deterministický Turingův stroj M a polynomy p, q tak, že pro každý vstupní řetězec X délky n = |X|,
- -li X je v L, pak
- -li X není v L, pak
Druhá podmínka zde může být přepsána jako
- -li X není v L, pak
Jak je uvedeno výše, z je údajný důkaz od Merlina (jehož velikost je ohraničena polynomem) a y je náhodný řetězec, který používá Arthur a který je také polynomiálně ohraničený.
Třída složitosti DOPOLEDNE[k] je sada problémů, o kterých lze rozhodnout v polynomiálním čase, s k dotazy a odpovědi. DOPOLEDNE jak je definováno výše je Dopoledne [2]. Dopoledne [3] začalo by jednou zprávou od Merlina Arturovi, potom zprávou od Arthura Merlinovi a nakonec zprávou od Merlina Arturovi. Poslední zpráva by měla být vždy od Merlina po Arthura, protože Arturovi nikdy nepomohlo poslat zprávu Merlinovi po rozhodnutí jeho odpovědi.
Vlastnosti

- Oba MA a DOPOLEDNE zůstanou beze změny, pokud se jejich definice změní tak, aby vyžadovaly dokonalou úplnost, což znamená, že Arthur přijme s pravděpodobností 1 (místo 2/3), když X je v jazyce.[1]
- Pro každou konstantu k ≥ 2, třída DOPOLEDNE[k] je rovný Dopoledne [2]. Li k může být polynomiálně vztaženo k velikosti vstupu, třídě DOPOLEDNE[poly (n)] se rovná třídě, IP, o kterém je známo, že se rovná PSPACE a je široce věřil, že je silnější než třída Dopoledne [2].
- MA je obsažen v DOPOLEDNE, od té doby DOPOLEDNE[3] obsahuje MA: Arthur může po obdržení Merlinova certifikátu otočit požadovaný počet mincí, poslat je Merlinovi a ignorovat odpověď.
- Je otevřené, zda DOPOLEDNE a MA jsou rozdílní. Pod věrohodným obvodem dolní hranice (podobné těm, které naznačují P=BPP), oba jsou si rovni NP.[2]
- DOPOLEDNE je stejný jako třída BP.NP kde BP označuje pravděpodobnostní operátor s omezenou chybou. Taky, (také psáno jako Existuje BBP) je podmnožinou MA. Zda MA je rovný je otevřená otázka.
- Konverze na soukromý coin coin protokol, ve kterém Merlin nemůže předvídat výsledek Arturových náhodných rozhodnutí, zvýší počet kol interakce o maximálně 2 v obecném případě. Takže verze soukromé mince DOPOLEDNE se rovná verzi s veřejnou mincí.
- MA obsahuje obojí NP a BPP. Pro BPP je to okamžité, protože Arthur může jednoduše ignorovat Merlina a vyřešit problém přímo; pro NP musí Merlin poslat Arturovi pouze certifikát, který Arthur může deterministicky ověřit v polynomiálním čase.
- Oba MA a DOPOLEDNE jsou obsaženy v polynomiální hierarchie. Zejména, MA je obsažen v průsečíku Σ2P a Π2P a DOPOLEDNE je obsažen v Π2P. Ještě více, MA je obsažen v podtřídě SP
2,[3] třída složitosti vyjadřující „symetrické střídání“. Toto je zobecnění Sipser – Lautemannova věta. - DOPOLEDNE je obsažen v NP / poly, třída rozhodovacích problémů vypočítatelná v nedeterministickém polynomiálním čase s velikostí polynomu Rada. Důkazem je variace Adlemanova věta.
- MA je obsažen v PP; tento výsledek je způsoben Vereshchaginem.[4]
- MA je obsažen v jeho kvantové verzi, QMA.[5]
- DOPOLEDNE obsahuje problém rozhodnutí, zda jsou dva grafy ne izomorfní. Protokol využívající soukromé mince je následující a lze jej transformovat na veřejný protokol o mincích. Vzhledem ke dvěma grafům G a H, Arthur náhodně vybere jeden z nich a zvolí náhodnou permutaci svých vrcholů, představující permutovaný graf Já Merlinovi. Merlin musí odpovědět, pokud Já byl vytvořen z G nebo H. Pokud jsou grafy neizomorfní, bude Merlin schopen s plnou jistotou odpovědět (kontrolou, zda Já je izomorfní s G). Pokud jsou však grafy izomorfní, je možné obojí G nebo H byl použit k vytvoření Jáa stejně pravděpodobné. V tomto případě je Merlin nemá žádný způsob, jak je rozeznat a dokáže Artura přesvědčit s největší pravděpodobností 1/2, což lze opakováním zesílit na 1/4. Toto je ve skutečnosti a nulový důkaz znalostí.
- Li DOPOLEDNE obsahuje coNP pak PH = DOPOLEDNE. To dokazuje, že je nepravděpodobné, že izomorfismus grafů bude NP-úplný, protože implikuje kolaps polynomiální hierarchie.
- Je známo, za předpokladu ERH, to pro každého d problém „Vzhledem k souboru vícerozměrných polynomů každý s celočíselnými koeficienty a stupněm maximálně d, mají společnou komplexní nulu? “je v DOPOLEDNE.[6]
Reference
- ^ Důkaz viz Rafael Pass a Jean-Baptiste Jeannin (24. března 2009). „Lecture 17: Arthur-Merlin games, Zero-knowledge proofs“ (PDF). Citováno 23. června 2010.
- ^ Impagliazzo, Russell; Wigderson, Avi (04.05.1997). P = BPP, pokud E vyžaduje exponenciální obvody: derandomizace lemmatu XOR. ACM. str. 220–229. doi:10.1145/258533.258590. ISBN 0897918886.
- ^ „Symetrická alternace zachycuje BPP“ (PDF). Ccs.neu.edu. Citováno 2016-07-26.
- ^ Vereschchagin, N.K. (1992). "Na síle PP". [1992] Proceedings of the Seventh Annual Structure in Complexity Theory Conference. str. 138–143. doi:10.1109 / sct.1992.215389. ISBN 081862955X.
- ^ Vidick, Thomas; Watrous, John (2016). „Kvantové důkazy“. Základy a trendy v teoretické informatice. 11 (1–2): 1–215. arXiv:1610.01664. doi:10.1561/0400000068. ISSN 1551-305X.
- ^ "Předmět: Algebra a výpočet". People.csail.mit.edu. Citováno 2016-07-26.
Bibliografie
- Babai, László (1985), „Trading group theory for randomness“, STOC '85: Sborník ze sedmnáctého ročníku sympozia ACM o teorii práce s počítačem, ACM, str. 421–429, ISBN 978-0-89791-151-1.
- Goldwasser, Shafi; Sipser, Michael (1986), „Soukromé mince versus veřejné mince v interaktivních důkazních systémech“, STOC '86: Sborník z osmnáctého ročníku ACM symposia o teorii práce s počítačem, ACM, str. 59–68, ISBN 978-0-89791-193-1.
- Arora, Sanjeev; Barak, Boaz (2009), Výpočetní složitost: moderní přístup, Cambridge, ISBN 978-0-521-42426-4.
- Kurz MIT Madhu Sudan o pokročilé složitosti