Protocolo Arthur-Merlin

Question

Recientemente aprendí sobre el Protocolo de Arthur-Merlin, y definimos las clases de complejidad $ am, ma $ .

También hemos visto que existe un teorema que indica que $ amamam ... am= am $ , sin embargo, no hemos definido formalmente $ amamamam ... am $ .

Damos una breve definición para ello como un protocolo, pero me gustaría ver una definición formal sin protocolos , al igual que $ am $ y $ mA $ (y $ mam $ )

Una definición para $ ama $ debe ser suficiente para mí, solo para tener el ánimo de cómo debe mirar.

¡Gracias!

Answer 1

$ ama $ es básicamente un sistema de prueba interactivo de 3 rondas donde el verificador (Arthur) solo se le permite enviar aleatoriedad al Prover (Merlín).
Todavía no he visto una definición tan explícita, pero creo que podemos formularlo de la siguiente manera. La primera ronda de AM [3] comienza con Merlin enviando un mensaje $ m_1 $ a Arthur. En la segunda ronda, Arthur envía la aleatoriedad $ r $ a Merlín, que le sigue la tercera ronda final en la que Merlin envía un mensaje $ m_2 $ . Arthur luego decide aceptar / rechazar usando un verificador de tiempo polinomial determinista $ v $ .

Creo que podemos definir la clase de la siguiente manera.
Definición: $ l ∈ ama $ Si existe un algoritmo determinista de poliezo $ v $ tal que:

• si $ x \ en l \; (| x |= n) $ luego $ \ existe P. pr_ {r \ in \ {0,1 \} ^ {p (n)}} \ \ izquierda (V (x, m_1, r, m_2)= 1 \ derecha) \ ge 2/3 $ donde $ \; m_1= p (x), \; m_2= P (x, r) $
• si $ x \ notin l \; (| x |= n) $ luego $ \ forall p. pr_ {r \ in \ {0,1 \} ^ {p (n)}} \ \ a la izquierda (V (x, m_1, r, m_2)= 1 \ derecha) \ le 1/3 $ donde $ \; m_1= p (x), \; m_2= P (x, r) $

Nota El Prover $ P $ es una función $ P: \ {0,1 \} ^ * \ Rudowarrow \ {0,1}} ^ {Q (n)} $ , donde $ q (n) $ es un polinomio.

Ver: compresa computacional por la sección 8.1.