Protokół Arthura – Merlina - Arthur–Merlin protocol

W teorii złożoności obliczeniowej , protokół Arthura – Merlina , wprowadzony przez Babai (1985) , jest interaktywnym systemem dowodowym, w którym rzuty monetą weryfikatora są ograniczone jako publiczne (tj. Znane również dowodzącemu). Goldwasser i Sipser (1986) udowodnił, że wszystkie (formal) języków z interaktywnymi dowodów dowolnej długości z prywatnymi monet mają także interaktywne dowodów monet publicznych.

Biorąc pod uwagę dwóch uczestników protokołu o nazwach odpowiednio Arthur i Merlin, podstawowe założenie jest takie, że Arthur jest standardowym komputerem (lub weryfikatorem) wyposażonym w urządzenie generujące liczby losowe , podczas gdy Merlin jest faktycznie wyrocznią o nieskończonej mocy obliczeniowej (znanej również jako przysłowia) ). Jednak Merlin niekoniecznie jest uczciwy, więc Artur musi przeanalizować informacje dostarczone przez Merlina w odpowiedzi na zapytania Arthura i sam zdecydować o problemie. Problemem jest uważany za rozwiązywalne przez ten protokół, jeśli kiedykolwiek odpowiedź brzmi „tak”, Merlin ma jakąś serię reakcji co spowoduje Arthur przyjmować co najmniej ² / ₃ czasu, a jeśli kiedykolwiek odpowiedź brzmi „nie” Arthur nigdy nie zaakceptuje więcej niż ¹ / ₃ czasu. W ten sposób Arthur działa jako probabilistyczny weryfikator czasu wielomianowego, zakładając, że jest przydzielony wielomianowy czas na podejmowanie decyzji i zapytań.

MAMA

Najprostszym takim protokołem jest protokół 1-wiadomości, w którym Merlin wysyła Arturowi wiadomość, a następnie Artur decyduje, czy zaakceptować, czy nie, uruchamiając probabilistyczne obliczenie czasu wielomianu. (Jest to podobne do definicji NP opartej na weryfikatorze, jedyną różnicą jest to, że Arthur może tutaj używać losowości). Merlin nie ma dostępu do rzutów monetą Arthura w tym protokole, ponieważ jest to protokół z pojedynczą wiadomością, a Arthur rzuca monetami dopiero po otrzymaniu wiadomości Merlina. Ten protokół nazywa się MA . Nieformalnie język L jest w MA, jeśli dla wszystkich ciągów w języku istnieje dowód wielkości wielomianu, że Merlin może wysłać Artura, aby przekonał go o tym z dużym prawdopodobieństwem, a dla wszystkich ciągów nie w języku nie ma dowodu, że przekonuje Arthura z dużym prawdopodobieństwem.

Formalnie klasa złożoności MA jest zbiorem problemów decyzyjnych, które można rozstrzygnąć w czasie wielomianowym za pomocą protokołu Arthura – Merlina, w którym jedyny ruch Merlina poprzedza jakiekolwiek obliczenia wykonane przez Arthura. Innymi słowy, język L jest w MA, jeśli istnieje wielomianowa probabilistyczna maszyna Turinga M i wielomiany p , q takie, że dla każdego ciągu wejściowego x o długości n = | x |,

• jeśli x jest w L , to ${\ Displaystyle \ istnieje z \ w \ {0,1 \} ^ {q (n)} \, \ Pr \ nolimits _ {y \ in \ {0,1 \} ^ {p (n)}} (M (x, y, z) = 1) \ geq 2/3,}$
• jeśli x nie jest w L , to ${\ displaystyle \ forall z \ in \ {0,1 \} ^ {q (n)} \, \ Pr \ nolimits _ {y \ in \ {0,1 \} ^ {p (n)}} (M (x, y, z) = 0) \ geq 2/3.}$

Drugi warunek można alternatywnie zapisać jako

• jeśli x nie jest w L , to ${\ displaystyle \ forall z \ in \ {0,1 \} ^ {q (n)} \, \ Pr \ nolimits _ {y \ in \ {0,1 \} ^ {p (n)}} (M (x, y, z) = 1) \ leq 1/3.}$

Aby porównać to z nieformalną definicją powyżej, z jest rzekomym dowodem od Merlina (którego rozmiar jest ograniczony wielomianem), a y jest losowym ciągiem, którego używa Arthur, który jest również ograniczony wielomianem.

JESTEM

Klasa złożoności AM (lub AM [2] ) to zbiór problemów decyzyjnych , które można rozstrzygnąć w czasie wielomianowym przez protokół Arthur-Merlin z dwoma komunikatami. Jest tylko jedna para zapytanie / odpowiedź: Artur rzuca kilka losowych monet i wysyła wynik wszystkich swoich rzutów monetą do Merlina, Merlin odpowiada rzekomym dowodem, a Artur deterministycznie weryfikuje dowód. W tym protokole Artur może wysyłać tylko wyniki rzutów monetą do Merlina, a na ostatnim etapie Artur musi zdecydować, czy zaakceptować, czy odrzucić, używając tylko swoich wcześniej wygenerowanych losowych rzutów monetą i wiadomości Merlina.

Innymi słowy, język L jest w AM, jeśli istnieje deterministyczna maszyna Turinga M w czasie wielomianu i wielomiany p , q takie, że dla każdego ciągu wejściowego x o długości n = | x |,

• jeśli x jest w L , to ${\ Displaystyle \ Pr \ nolimits _ {y \ in \ {0,1 \} ^ {p (n)}} (\ istnieje z \ w \ {0,1 \} ^ {q (n)} \, M (x, y, z) = 1) \ geq 2/3,}$
• jeśli x nie jest w L , to ${\ displaystyle \ Pr \ nolimits _ {y \ in \ {0,1 \} ^ {p (n)}} (\ forall z \ in \ {0,1 \} ^ {q (n)} \, M (x, y, z) = 0) \ geq 2/3.}$

Drugi warunek tutaj można przepisać jako

• jeśli x nie jest w L , to ${\ Displaystyle \ Pr \ nolimits _ {y \ in \ {0,1 \} ^ {p (n)}} (\ istnieje z \ w \ {0,1 \} ^ {q (n)} \, M (x, y, z) = 1) \ leq 1/3.}$

Jak powyżej, z jest rzekomym dowodem od Merlina (którego rozmiar jest ograniczony wielomianem), a y jest losowym ciągiem, którego używa Arthur, który jest również ograniczony wielomianem.

Klasa złożoności AM [ k ] jest zbiorem problemów, które można rozstrzygnąć w czasie wielomianowym, z k zapytaniami i odpowiedziami. PM jest zdefiniowane jako PM [2] . AM [3] zaczynałby się od jednej wiadomości od Merlina do Artura, potem od Artura do Merlina, a na końcu od Merlina do Artura. Ostatnia wiadomość powinna zawsze być od Merlina do Artura, ponieważ Arthurowi nigdy nie pomaga wysłanie wiadomości do Merlina po podjęciu decyzji o udzieleniu odpowiedzi.

Nieruchomości

Znane związki MA i AM z innymi klasami złożoności. Strzałka z klasy A do klasy B oznacza jest podzbiorem B .

• Zarówno MA, jak i AM pozostają niezmienione, jeśli ich definicje zostaną zmienione tak, aby wymagały doskonałej kompletności, co oznacza, że ​​Arthur akceptuje z prawdopodobieństwem 1 (zamiast 2/3), gdy x jest w języku.
• Dla dowolnej stałej k ≥ 2 klasa AM [ k ] jest równa AM [2] . Jeśli k można wielomianowo powiązać z wielkością wejściową, klasa AM [poly ( n )] jest równa klasie IP , o której wiadomo, że jest równa PSPACE i powszechnie uważa się, że jest silniejsza niż klasa AM [2] .
• MA jest zawarte w AM , ponieważ AM [3] zawiera MA : Arthur może, po otrzymaniu certyfikatu Merlina, obrócić wymaganą liczbę monet, wysłać je do Merlina i zignorować odpowiedź.
• Jest otwarte, czy AM i MA są różne. Pod prawdopodobnymi dolnymi granicami obwodu (podobnymi do tych, które sugerują P = BPP ), są one równe NP .
• AM jest tym samym, co klasa BP⋅NP, gdzie BP oznacza operator probabilistyczny błędu ograniczonego. Ponadto (napisane również jako ExistsBPP ) jest podzbiorem MA . To, czy MA jest równe, jest kwestią otwartą. ${\ displaystyle \ exist \ cdot {\ mathsf {BPP}}}$${\ displaystyle \ exist \ cdot {\ mathsf {BPP}}}$
• Konwersja na prywatny protokół monet, w którym Merlin nie może przewidzieć wyniku losowych decyzji Artura, zwiększy liczbę rund interakcji o co najwyżej 2 w ogólnym przypadku. Tak więc wersja AM na monety prywatne jest równa wersji z monetą publiczną.
• MA zawiera zarówno NP, jak i BPP . W przypadku BPP jest to natychmiastowe, ponieważ Arthur może po prostu zignorować Merlina i bezpośrednio rozwiązać problem; w przypadku NP Merlin musi tylko wysłać Arthurowi certyfikat, który Arthur może zweryfikować deterministycznie w czasie wielomianowym.
• Zarówno MA, jak i AM są zawarte w hierarchii wielomianów . W szczególności, MA znajduje się na przecięciu Ď ₂ ^P i gatunku ₂ ^P i PM jest zawarty w gatunku ₂ ^P . Co więcej, MA jest zawarte w podklasie S. ^P
  ₂ , klasa złożoności wyrażająca „przemianę symetryczną”. Jest to uogólnienie twierdzenia Sipsera – Lautemanna .
• AM jest zawarte w NP / poli , klasie problemów decyzyjnych obliczalnych w niedeterministycznym czasie wielomianowym z radą dotyczącą wielkości wielomianu . Dowód jest odmianą twierdzenia Adlemana .
• MA jest zawarte w PP ; ten wynik jest zasługą Vereshchagina.
• MA jest zawarte w wersji kwantowej QMA .
• AM zawiera problem rozstrzygnięcia, czy dwa wykresy nie są izomorficzne. Protokół wykorzystujący monety prywatne jest następujący i można go przekształcić w protokół monet publicznych. Mając dwa wykresy G i H , Arthur losowo wybiera jeden z nich i wybiera losową permutację jego wierzchołków, przedstawiając permutowany wykres I do Merlina. Merlin musi odpowiedzieć, czy ja został stworzony z G lub H . Jeśli wykresy są nieizomorficzne, Merlin będzie mógł odpowiedzieć z pełną pewnością (sprawdzając, czy I jest izomorficzny do G ). Jeśli jednak wykresy są izomorficzne, możliwe jest, że do stworzenia I użyto G lub H , i równie prawdopodobne. W tym przypadku Merlin nie ma sposobu, aby je rozróżnić i może przekonać Artura z prawdopodobieństwem najwyżej 1/2, a powtórzenie to można zwiększyć do 1/4. W rzeczywistości jest to dowód wiedzy zerowej .
• Jeśli AM zawiera coNP, to PH = AM . Jest to dowód na to, że izomorfizm wykresu prawdopodobnie nie będzie NP-zupełny, ponieważ implikuje załamanie się hierarchii wielomianów.
• Wiadomo, zakładając ERH , że dla dowolnego d problem „Biorąc pod uwagę zbiór wielomianów wielowymiarowych, z których każdy ma współczynniki całkowite i stopień co najwyżej d , czy mają one wspólne zero zespolone?” jest w AM . ${\ displaystyle f_ {i}}$

Bibliografia

Bibliografia

• Babai, László (1985), "Trading group teoria losowości", STOC '85: Proceedings of the siedemnastego dorocznego sympozjum ACM na temat teorii obliczeń , ACM, str. 421–429, ISBN   978-0-89791-151-1 .
• Goldwasser, Shafi ; Sipser, Michael (1986), „Monety prywatne a monety publiczne w interaktywnych systemach dowodowych”, STOC '86: Proceedings of the osiemnastego dorocznego sympozjum ACM on Theory of computing , ACM, str. 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 .
• Kurs MIT Madhu Sudan dotyczący zaawansowanej złożoności

Linki zewnętrzne

• Zoo złożoności : MA
• Zoo złożoności : AM