Public-coin

Интерактивное доказательство с общедоступной монетой (interactive public coin proof), известное так же, как Игра Артур-Мерлин (Arthur-Merlin game) - интерактивное доказательство, в котором Проверяющий генерирует случайные величины, отсылает их Доказывающему, и вырабатывает окончательное решение, принимать или отвергать доказательство.

Название public coin образовалось из-за генерации случайных бит ("подбрасывание монеты", "coin flipping"), которые доступны и Проверяющему и Доказывающему.

Arthur-Merlin game

В игре Артур-Мерлин Проверяющий (называемый Артуром) в каждом раунде выбирает строку v ∈ U{0,1}индекс l,

где l ∈ ℕ и меняется от раунда к раунду. Артур посылает эту строку Доказывающему (называемому Мерлином). Какие-либо другие сообщения от Артура к Мерлину не посылаются.

Определения

Пусть α и β — функции из ℕ в ℝ.

Пара интерактивных вероятностных алгоритмов (P, V), в которой V полиномиален, называется протоколом интерактивного доказательства для языка L с границей полноты α и границей корректности β, если:

1. Pr(⟨P, V⟩(x) = 1 ⩾ α(|x|), для ∀x ∈ L (условие полноты протокола);

1. Pr(⟨P′, V⟩(x) = 1) ⩽ β(|x|), для ∀x ∈ {0,1}∗ ∖ L и для ∀P′ - интерактивного вероятностного алгоритма (условие корректности протокола).

Принцип работы

Пусть k — произвольная функция из ℕ в {r ∈ ℝ | r ⩾ 0}.

Класс AM[k] определяется как класс всех языков L, для которых существует игра Артура и Мерлина с границей полноты 2/3 и границей корректности 1/3, выполняющаяся не более k раундов и удовлетворяющая следующим условиям:

1. Выполнение протокола инициирует Артур.
2. После выполнения ⌊k(|x|)⌋ раундов, где x — общий вход Артура и Мерлина, Артур должен принять или отвергнуть доказательство.

Примечание

Класс MA[k] определяется аналогично классу AM[k] с той лишь разницей, что выполнение протокола инициирует Мерлин.

На главную страницу раздела

Ларина Т.М., 2016