Игра Артура и Мерлина
Игрой Артура и Мерлина называется протокол интерактивного доказательства, в котором проверяющий (называемый Артуром) в каждом раунде выбирает строку $v\in_{\mathfrak U}\{0,1\}^l$ при некотором $l\in\mathbb N$ (вообще говоря, $l$ меняется от раунда к раунду) и посылает эту строку доказывающему (называемому Мерлином). Какие либо другие сообщения от Артура к Мерлину не посылаются. Имена персонажей взяты из британского эпоса, в котором мудрец и волшебник Мерлин был наставником и помощником короля Артура.
Пусть $k$ — произвольная функция из $\mathbb N$ в $\{r\in\mathbb R\,|\, r\geqslant0\}$. Класс $\mathrm{AM}[k]$ определяется как класс всех языков $L$, для которых существует игра Артура и Мерлина с границей полноты $2/3$ и границей корректности $1/3$, выполняющаяся не более $k$ раундов и удовлетворяющая следующим двум дополнительным условиям. Во-первых, выполнение протокола инициирует Артур. Во-вторых, после выполнения $\lfloor k(\lvert{x}\rvert)\rfloor$ раундов (где $x$ — общий вход Артура и Мерлина) Артур не имеет права использовать случайные биты, а должен детерминированным образом вычислить свое выходное значение, т. е. принять или отвергнуть доказательство. Класс $\mathrm{MA}[k]$ определяется аналогично классу $\mathrm{AM}[k]$ с той лишь разницей, что выполнение протокола инициирует Мерлин. Для классов $\mathrm{AM}[k]$ и $\mathrm{MA}[k]$ справедлив естественный аналог предложения 2 из статьи Протокол интерактивного доказательства (разумеется, вышеуказанные дополнительные условия также следует добавить в условия 2 и 3 этого предложения).
Из этой теоремы следует, что класс всех языков, для которых существует игра Артура и Мерлина с границей полноты $2/3$ и границей корректности $1/3$, совпадает с $\mathrm{IP}$ (а $\mathrm{IP}$, в свою очередь, совпадает с $\mathrm{PSPACE}$ — см. теорему 3 из статьи Протокол интерактивного доказательства).
Пусть $c\in\mathbb N\setminus\{0\}$. Тогда класс $\mathrm{AM}[c]$ ($\mathrm{MA}[c]$) обозначается словом длины $c$ из чередующихся букв $\mathrm A$ и $\mathrm M$, начинающимся с $\mathrm A$ (соответственно, с $\mathrm M$). А именно, $\mathrm{AM}[1]=\mathrm A$, $\mathrm{MA}[1]=\mathrm M$, $\mathrm{AM}[2]=\mathrm{AM}$, $\mathrm{MA}[2]=\mathrm{MA}$, $\mathrm{AM}[3]=\mathrm{AMA}$, $\mathrm{MA}[3]=\mathrm{MAM}$ и т. д.
- $\mathrm{AM}[c]\cup\mathrm{MA}[c]\subseteq \mathrm{AM}[c+1]\cap\mathrm{MA}[c+1]$ для любой константы $c\in\mathbb N\setminus\{0\}$;
- $\mathrm A=\mathrm{BPP}$, $\mathrm M=\mathrm{NP}$;
- $\mathrm{AM}=\mathrm{AM}[d]=\mathrm{MA}[d']$ для любых констант $d,d’\in\mathbb N$ таких, что $d\geqslant2$ и $d’\geqslant3$;
- $\mathrm{AM}\subseteq\Pi_2^{\mathrm P}$, $\mathrm{MA}\subseteq\Sigma_2^{\mathrm P}\cap\Pi_2^{\mathrm P}$.
Из теоремы 1 и п. 3 теоремы 2 вытекает
Литература
- [1] Goldwasser, S. and Sipser, M. «Private coins versus public coins in interactive proof systems» 1986
- [2] Goldwasser, S. and Sipser, M. «Private coins versus public coins in interactive proof systems» 1989
- [3] Arora, S. and Barak, B. «Computational complexity: A modern approach» 2007
- [4] Babai, L «Trading Group Theory for Randomness» 1985
- [5] Babai, L. and Moran, S. «Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes» 1988