Протокол Артура–Мерлина
-
Определение и свойства MA и AM
- MA — это класс задач, которые могут быть решены за полиномиальное время с помощью вероятностного оракула.
- AM — это класс задач, решаемых за полиномиальное время с использованием протокола Артура-Мерлина.
- MA и AM остаются неизменными при изменении требований к полноте.
- AM[k] — это класс задач, решаемых с помощью k запросов и ответов, и AM[2] — это AM.
- AM[3] включает в себя три сообщения: одно от Мерлина Артуру, одно от Артура Мерлину и одно от Мерлина Артуру.
-
Сравнение MA и AM
- MA содержит AM, и AM[3] содержит MA.
- Неизвестно, отличаются ли MA и AM друг от друга.
- При вероятностных нижних границах схемы оба класса равны NP.
- MA является подмножеством BP⋅NP и содержит как NP, так и BPP.
- MA содержится в полиномиальной иерархии и в подклассе SP2.
- AM содержит задачу определения неизоморфности графов.
-
Доказательство с нулевым разглашением
- В AM существует доказательство с нулевым разглашением, которое может быть преобразовано в протокол публичных монет.
- Если AM содержит coNP, то PH = AM, что указывает на возможное разрушение полиномиальной иерархии.
-
Рекомендации
- Ссылки на курс Мадху Судана и на «Зоопарк сложности» для дополнительной информации.
Полный текст статьи: