Protocolul Arthur – Merlin - Arthur–Merlin protocol

În teoria complexității de calcul , un protocol Arthur – Merlin , introdus de Babai (1985) , este un sistem interactiv de probă în care aruncările de monede ale verificatorului sunt constrânse să fie publice (adică cunoscute și de prover). Goldwasser & Sipser (1986) au demonstrat că toate limbile (formale) cu dovezi interactive de lungime arbitrară cu monede private au și dovezi interactive cu monede publice.

Având în vedere doi participanți la protocolul numit Arthur și respectiv Merlin, presupunerea de bază este că Arthur este un computer standard (sau verificator) echipat cu un dispozitiv generator de numere aleatorii , în timp ce Merlin este efectiv un oracol cu putere de calcul infinită (cunoscut și sub numele de prover ). Cu toate acestea, Merlin nu este neapărat cinstit, așa că Arthur trebuie să analizeze informațiile furnizate de Merlin ca răspuns la întrebările lui Arthur și să decidă problema în sine. O problemă este considerată a fi rezolvabile prin acest protocol , dacă de fiecare dată când răspunsul este „da“, Merlin are unele serie de răspunsuri , care va determina Arthur să accepte cel puțin cu ² / cu ₃ din timp, iar în cazul în care de fiecare dată când răspunsul este „nu“ , Arthur nu va accepta mai mult de ¹ / cu ₃ din timp. Astfel, Arthur acționează ca un verificator probabilist de timp polinomial, presupunând că este alocat timp polinomial pentru a lua deciziile și interogările sale.

MA

Cel mai simplu astfel de protocol este protocolul cu 1 mesaj în care Merlin îi trimite lui Arthur un mesaj, iar apoi Arthur decide dacă acceptă sau nu executând un calcul probabilistic al timpului polinomial. (Aceasta este similară definiției bazate pe verificator a NP, singura diferență fiind că Arthur are voie să folosească aleatoriu aici.) Merlin nu are acces la aruncările de monede ale lui Arthur în acest protocol, deoarece este un protocol cu ​​un singur mesaj și Arthur își aruncă monedele numai după ce a primit mesajul lui Merlin. Acest protocol se numește MA . În mod informal, un limbaj L este în MA dacă pentru toate șirurile din limbă există o dovadă polinomială conform căreia Merlin îl poate trimite pe Arthur să-l convingă de acest fapt cu mare probabilitate, iar pentru toate șirurile care nu se află în limbă nu există nicio dovadă că îl convinge pe Arthur cu mare probabilitate.

În mod formal, clasa de complexitate MA este setul de probleme de decizie care pot fi decise în timp polinomial printr-un protocol Arthur-Merlin unde singura mișcare a lui Merlin precede orice calcul de către Arthur. Cu alte cuvinte, un limbaj L este în MA dacă există o mașină Turing probabilistică în timp polinomial M și polinomii p , q astfel încât pentru fiecare șir de intrare x de lungime n = | x |,

• dacă x este în L , atunci ${\ displaystyle \ există z \ in \ {0,1 \} ^ {q (n)} \, \ Pr \ nolimits _ {y \ in \ {0,1 \} ^ {p (n)}} (M (x, y, z) = 1) \ geq 2/3,}$
• dacă x nu este în L , atunci ${\ displaystyle \ forall z \ in \ {0,1 \} ^ {q (n)} \, \ Pr \ nolimits _ {y \ in \ {0,1 \} ^ {p (n)}} (M (x, y, z) = 0) \ geq 2/3.}$

A doua condiție poate fi scrisă alternativ ca

• dacă x nu este în L , atunci ${\ displaystyle \ forall z \ in \ {0,1 \} ^ {q (n)} \, \ Pr \ nolimits _ {y \ in \ {0,1 \} ^ {p (n)}} (M (x, y, z) = 1) \ leq 1/3.}$

Pentru a compara acest lucru cu definiția informală de mai sus, z este pretinsa dovadă de la Merlin (a cărei dimensiune este delimitată de un polinom) și y este șirul aleatoriu pe care Arthur îl folosește, care este, de asemenea, delimitat polinomial.

A.M

Clasa de complexitate AM (sau AM [2] ) este setul de probleme de decizie , care pot fi decise în timp polinomial printr - un protocol de Arthur-Merlin , cu două mesaje. Există o singură pereche de întrebări / răspunsuri: Arthur aruncă câteva monede aleatorii și trimite rezultatul tuturor aruncărilor sale de monede către Merlin, Merlin răspunde cu o dovadă pretinsă, iar Arthur verifică deterministic dovada. În acest protocol, Arthur are voie să trimită rezultatele aruncărilor de monede către Merlin și, în etapa finală, Arthur trebuie să decidă dacă acceptă sau respinge folosind doar întoarcerile sale aleatorii generate anterior și mesajul lui Merlin.

Cu alte cuvinte, un limbaj L este în AM dacă există o mașină de determinare a timpului polinomial M și polinoamele p , q astfel încât pentru fiecare șir de intrare x de lungime n = | x |,

• dacă x este în L , atunci ${\ displaystyle \ Pr \ nolimits _ {y \ in \ {0,1 \} ^ {p (n)}} (\ există z \ in \ {0,1 \} ^ {q (n)} \, M (x, y, z) = 1) \ geq 2/3,}$
• dacă x nu este în L , atunci ${\ displaystyle \ Pr \ nolimits _ {y \ in \ {0,1 \} ^ {p (n)}} (\ forall z \ in \ {0,1 \} ^ {q (n)} \, M (x, y, z) = 0) \ geq 2/3.}$

A doua condiție aici poate fi rescrisă ca

• dacă x nu este în L , atunci ${\ displaystyle \ Pr \ nolimits _ {y \ in \ {0,1 \} ^ {p (n)}} (\ există z \ in \ {0,1 \} ^ {q (n)} \, M (x, y, z) = 1) \ leq 1/3.}$

Ca mai sus, z este pretinsa dovadă de la Merlin (a cărei dimensiune este mărginită de un polinom) și y este șirul aleatoriu pe care îl folosește Arthur, care este, de asemenea, mărginit polinomial.

Clasa de complexitate AM [ k ] este ansamblul de probleme care pot fi decise în timp polinomial, cu k interogări și răspunsuri. AM așa cum s-a definit mai sus este AM [2] . AM [3] ar începe cu un mesaj de la Merlin la Arthur, apoi un mesaj de la Arthur la Merlin și apoi în cele din urmă un mesaj de la Merlin la Arthur. Ultimul mesaj ar trebui să fie întotdeauna de la Merlin la Arthur, deoarece Arthur nu îi ajută niciodată să-i trimită un mesaj lui Merlin după ce a decis răspunsul său.

Proprietăți

Relații cunoscute ale MA și AM cu alte clase de complexitate. O săgeată de la clasa A la clasa B înseamnă A este un subset al B .

• Atât MA, cât și AM rămân neschimbate dacă definițiile lor sunt modificate pentru a necesita completitudinea perfectă, ceea ce înseamnă că Arthur acceptă cu probabilitatea 1 (în loc de 2/3) atunci când x este în limbă.
• Pentru orice constantă k ≥ 2, clasa AM [ k ] este egală cu AM [2] . Dacă k poate fi legat polinomial de dimensiunea intrării, clasa AM [poli ( n )] este egală cu clasa, IP , despre care se știe că este egală cu PSPACE și se crede că este mai puternică decât clasa AM [2] .
• MA este conținut în AM , deoarece AM [3] conține MA : Arthur poate, după primirea certificatului lui Merlin, să întoarcă numărul necesar de monede, să le trimită la Merlin și să ignore răspunsul.
• Este deschis dacă AM și MA sunt diferite. Sub limite plauzibile ale circuitului inferior (similare cu cele care implică P = BPP ), ambele sunt egale cu NP .
• AM este același cu clasa BP⋅NP unde BP denotă operatorul probabilist cu eroare mărginită. De asemenea, (scris și ca ExistsBPP ) este un subset al MA . Dacă MA este egal cu este o întrebare deschisă. ${\ displaystyle \ există \ cdot {\ mathsf {BPP}}}$${\ displaystyle \ există \ cdot {\ mathsf {BPP}}}$
• Conversia la un protocol de monedă privată, în care Merlin nu poate prezice rezultatul deciziilor aleatorii ale lui Arthur, va crește numărul de runde de interacțiune cu cel mult 2 în cazul general. Deci, versiunea cu monedă privată a AM este egală cu versiunea cu monedă publică.
• MA conține atât NP, cât și BPP . Pentru BPP, acest lucru este imediat, deoarece Arthur poate pur și simplu să-l ignore pe Merlin și să rezolve problema direct; pentru NP, Merlin trebuie doar să îi trimită lui Arthur un certificat, pe care Arthur îl poate valida în mod determinist în timp polinomial.
• Atât MA, cât și AM sunt conținute în ierarhia polinomială . În special, MA este conținută în intersecția Σ ₂ ^P și Π ₂ ^P și AM este conținută în Π ₂ ^P . Mai mult, MA este conținut în subclasa S ^P
  ₂ , o clasă de complexitate care exprimă „alternanța simetrică”. Aceasta este o generalizare a teoremei Sipser – Lautemann .
• AM este conținut în NP / poly , clasa problemelor de decizie calculabile în timp polinomial nedeterminist cu un sfat de dimensiune polinomială . Dovada este o variantă a teoremei lui Adleman .
• AM este conținut în PP ; acest rezultat se datorează Vereshchagin.
• MA este conținut în versiunea sa cuantică, QMA .
• AM conține problema de a decide dacă două grafice nu sunt izomorfe. Protocolul care utilizează monede private este următorul și poate fi transformat într-un protocol public de monede. Având în vedere două grafice G și H , Arthur alege aleatoriu unul dintre ele și alege o permutare aleatorie a vârfurilor sale, prezentând graficul permutat I lui Merlin. Merlin trebuie să răspundă dacă am fost creat de la G sau H . Dacă graficele sunt nonizomorfe, Merlin va putea răspunde cu certitudine deplină (verificând dacă I este izomorfă la G ). Cu toate acestea, dacă graficele sunt izomorfe, este posibil ca G sau H să fie utilizate pentru a crea I , și la fel de probabil. În acest caz, Merlin nu are nicio modalitate de a le deosebi și îl poate convinge pe Arthur cu probabilitate de cel mult 1/2, iar acest lucru poate fi amplificat la 1/4 prin repetare. Aceasta este de fapt o dovadă de cunoaștere zero .
• Dacă AM conține coNP atunci PH = AM . Aceasta este o dovadă că este puțin probabil ca izomorfismul grafic să fie complet NP, deoarece implică prăbușirea ierarhiei polinomiale.
• Se știe, presupunând ERH , că pentru orice d problema "Având în vedere o colecție de polinoame multivariate fiecare cu coeficienți întregi și de grad cel mult d , au un complex comun zero?" este în AM . ${\ displaystyle f_ {i}}$

Referințe

Bibliografie

• Babai, László (1985), "Trading group theory for randomness", STOC '85: Lucrările celui de-al șaptesprezecelea simpozion anual ACM pe teoria calculelor , ACM, pp. 421-429, ISBN   978-0-89791-151-1 .
• Goldwasser, Shafi ; Sipser, Michael (1986), "Monede private versus monede publice în sisteme interactive de probare ", STOC '86: Lucrările celui de-al XVIII-lea simpozion anual ACM pe teoria calculelor , ACM, pp. 59-68, ISBN   978-0-89791-193-1 .
• Arora, Sanjeev ; Barak, Boaz (2009), Computational Complexity: A Modern Approach , Cambridge , ISBN   978-0-521-42426-4 .
• Cursul MIT al Madhu Sudan privind complexitatea avansată

linkuri externe

• Gradina zoologica de complexitate : MA
• Gradina zoologica de complexitate : AM