Артур-Мерлин Протокол

Question

Я недавно узнал о протоколе Артур-Мерлин, и мы определили классы сложности $ am, ma $ .

Мы также видели, что существует теорема, заявив, что $ amamam ... am= am $ , однако мы официально не определены $ amamamam ... am $ .

Мы дали краткое определение для него в качестве протокола, но я хотел бы видеть формальное определение без протоколов , как и $ am $ и $ ma $ (и $ MAM $ )

Определение для $ AMA $ Должно быть достаточно для меня, просто чтобы посмотреть, как следует посмотреть.

Спасибо!

Answer 1

$ ama $ в основном является трехсторонней интерактивной системой доказательства, где верификатор (Артур) разрешен только для отправки случайности в Prover (Merlin).
Я еще не видел такого явного определения, но я думаю, что мы можем сформулировать его следующим образом. Первый раунд AM [3] начинается с Merlin, отправив сообщение $ m_1 $ до Артура. Во втором раунде Артур отправляет случайность $ R $ to Merlin, за которым следует последний третий раунд, в котором Мерлин отправляет сообщение $ l ∈ Ama $ Если существует многократный детерминированный алгоритм процентистика $ v $ такой, что:

.
• Если $ x \ in l \; (| x |= n) $ Тогда $ \ существует P. pr_ {r \ in \ {0,1 \} ^ {p (n)}} \ левый (v (x, m_1, r, m_2)= 1 \ верно) \ ge 2/3 $ где $ \; m_1= p (x), \; m_2= p (x, r) $
• Если $ x \ notin l \; (| x |= n) $ затем $ \ forall p. pr_ {r \ in \ {0,1 \} ^ {p (n)}} \ левый (v (x, m_1, r, m_2)= 1 \ верно) \ le 1/3 $ где $ \; m_1= p (x), \; m_2= p (x, r) $

Примечание. Prover $ P $ - это функция $ P: \ {0,1 \} ^ * \ prightarrow \ {0,1 \} ^ {q (n)} $ , где $ q (n) $ представляет собой полиномиальный.

См.: вычислительный жалобой от раздела Арора-Барака 8.1.