Protocolo Arthur-Merlin

Question

Eu aprendi recentemente sobre o protocolo Arthur-Merlin, e definimos as classes de complexidade $ am, MA $ .

Nós também vimos que existe um teorema afirmando que $ amamam ... am= am $ , no entanto, não definimos formalmente $ amamamam ... am $ .

Damos uma breve definição para isso como um protocolo, mas gostaria de ver uma definição formal sem protocolos , assim como $ AM $ e $ mA $ (e $ mamalk $ )

Uma definição para $ ama $ deve ser suficiente para mim, apenas para obter o jeito de como deveria olhar.

Obrigado!

Answer 1

$ ama $ é basicamente um sistema de prova interativa de 3 round, onde o verificador (Arthur) só é permitido enviar aleatoriedade para o provador (Merlin).
Eu ainda não vi uma definição tão explícita, mas acho que podemos formulá-lo como segue. A primeira rodada de AM [3] começa com Merlin enviando uma mensagem $ m_1 $ para Arthur. Na segunda rodada, Arthur envia aleatoriedade $ R $ para Merlin, que é seguido pela terceira rodada final em que Merlin envia uma mensagem $ m_2 $ . Arthur então decide aceitar / rejeitar o uso de verificador de tempo polinômico determinístico $ v $ .

Acho que podemos definir a classe da seguinte forma.
Definição: $ l ∈ AMA $ Se existe um algoritmo determinístico poli-time $ v $ tal que:

• se $ x \ in l \; (| x |= n) $ então $ \ existe p. pr_ {r \ in \ {0,1 \} ^ {p (n)}} \ left (v (x, m_1, r, m_2)= 1 \ direita) \ ge 2/3 $ onde $ \; m_1= p (x), \; m_2= p (x, r) $
• se $ x \ notin l \; (| x |= n) $ então $ \ forall p. pr_ {r \ in \ {0,1 \} ^ {p (n)}} \ left (v (x, m_1, r, m_2)= 1 \ direita) \ le 1/3 $ onde $ \; m_1= p (x), \; m_2= p (x, r) $

Observe o provador $ P $ é uma função $ p: \ {0,1 \} ^ * \ \ \ rightarrow \ {0,1 \} ^ {q (n)} $ , onde $ Q (n) $ é polinomial.

Veja: complexidade computacional da seção 8.1 de Arora-Barak.