Игра Артура и Мерлина

arthur-Merlin game

Синонимы: интерактивная система доказательства с общедоступной монетой

Связанные статьи: игра артур—мерлин (словарь), интерактивная система доказательства с общедоступной монетой (справочник)

Игрой Артура и Мерлина называется протокол интерактивного доказательства, в котором проверяющий (называемый Артуром) в каждом раунде выбирает строку $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 этого предложения).

Теорема 1 см. [1], [2], [3]

$\mathrm{IP}[k]\subseteq\mathrm{AM}[k+2]$ для любого полиномиального параметра $k$.

Из этой теоремы следует, что класс всех языков, для которых существует игра Артура и Мерлина с границей полноты $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}$ и т. д.

Теорема 2 см. [4], [5]

$\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 вытекает

Следствие 3

$\mathrm{AM}=\mathrm{IP}[d]=\mathrm{IP}[O(1)]$ для любой константы $d\in\mathbb N$ такой, что $d\geqslant2$.

Это следствие вместе с п. 4 теоремы 2 дает теорему 4 из статьи Протокол интерактивного доказательства.

Литература

[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

Математическая криптография

Игра Артура и Мерлина

Литература