Артур-Мерлин Протокол
-
29-09-2020 - |
Вопрос
Я недавно узнал о протоколе Артур-Мерлин, и мы определили классы сложности $ am, ma $ .
Мы также видели, что существует теорема, заявив, что $ amamam ... am= am $ , однако мы официально не определены $ amamamam ... am $ .
Мы дали краткое определение для него в качестве протокола, но я хотел бы видеть формальное определение
Определение для $ AMA $ Должно быть достаточно для меня, просто чтобы посмотреть, как следует посмотреть.
Спасибо!
Решение
$ 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.