Введение

В теории вычислительной сложности интерактивная система доказательств — это абстрактная машина, моделирующая вычисления как обмен сообщениями между двумя сторонами: доказывающим и проверяющим. Стороны взаимодействуют, обмениваясь сообщениями, чтобы установить, принадлежит ли заданная строка к языку или нет. Доказывающий обладает неограниченными вычислительными ресурсами, но ему нельзя доверять, в то время как проверяющий имеет ограниченную вычислительную мощность, но считается всегда честным. Обмен сообщениями между проверяющим и доказывающим продолжается до тех пор, пока проверяющий не получит ответ на задачу и не "убедится" в его правильности. Все интерактивные системы доказательств должны удовлетворять двум требованиям:
Полнота: если утверждение истинно, честный доказывающий (то есть тот, кто строго следует протоколу) может убедить честного проверяющего в его истинности. Корректность: если утверждение ложно, ни один доказывающий, даже нарушающий протокол, не сможет убедить честного проверяющего в его истинности, за исключением случая малой вероятности. Конкретные характеристики системы, и, следовательно, класс сложности языков, которые она может распознавать, зависят от ограничений, накладываемых на проверяющего, а также от предоставляемых ему возможностей — например, большинство интерактивных систем доказательств критически зависят от способности проверяющего совершать случайный выбор. Это также зависит от характера обмениваемых сообщений — их количества и содержимого. Было установлено, что интерактивные системы доказательств имеют важные последствия для традиционных классов сложности, определяемых с использованием только одной вычислительной машины. Основными классами сложности, описывающими интерактивные системы доказательств, являются AM и IP.

Предыстория

Каждая интерактивная система доказательств определяет формальный язык строк. Звучность системы доказательств относится к свойству, согласно которому ни один доказывающий не может заставить проверяющего принять неверное утверждение, за исключением некоторой малой вероятности. Верхняя граница этой вероятности называется ошибкой звучности системы доказательств. Более формально, для каждого доказывающего и для каждого :

для некоторого . Пока ошибка звучности ограничена полиномиальной долей от потенциального времени работы проверяющего (т.е. ), всегда можно усилить звучность до тех пор, пока ошибка звучности не станет пренебрежимо малой функцией относительно времени работы проверяющего. Это достигается путем повторения доказательства и принятия только в том случае, если все доказательства проходят проверку. После повторений, ошибка звучности будет уменьшена до .

НП

Класс сложности NP можно рассматривать как очень простую систему доказательств. В этой системе верификатор является детерминированной машиной, работающей за полиномиальное время (P-машина). Протокол следующий:
Доказывающий рассматривает входные данные и вычисляет решение, используя свои неограниченные возможности, а затем возвращает сертификат доказательства полиномиального размера. Верификатор проверяет, что сертификат является допустимым за детерминированное полиномиальное время. Если сертификат допустим, он принимает; в противном случае – отклоняет. Если существует допустимый сертификат, доказывающий всегда может заставить верификатора принять его, предоставив этот сертификат. Однако, если допустимого сертификата не существует, то входные данные не принадлежат языку, и ни один доказывающий, каким бы злонамеренным он ни был, не сможет убедить верификатора в обратном, поскольку любой сертификат будет отклонен.

Протоколы Артура Мерлина и Мерлина Артура

Хотя NP можно рассматривать как использующий взаимодействие, концепция вычисления посредством взаимодействия была сформулирована (в контексте теории сложности) двумя независимыми группами исследователей только в 1985 году. Один из подходов, предложенный Ласло Бабаем в его работе "Торговля теорией групп за случайность", определил иерархию классов Arthur–Merlin (AM). В этой модели Артур (проверяющий) – вероятностная машина, работающая за полиномиальное время, а Мерлин (доказывающий) обладает неограниченными ресурсами. Класс MA, в частности, является простым обобщением вышеописанного взаимодействия NP, в котором проверяющий является вероятностным, а не детерминированным. Кроме того, вместо строгого требования, чтобы проверяющий всегда принимал корректные доказательства и отклонял некорректные, он допускает некоторую гибкость:
Полнота: если строка принадлежит языку, доказывающий должен предоставить доказательство, которое проверяющий примет с вероятностью не менее 2/3 (в зависимости от случайного выбора проверяющего). Корректность: если строка не принадлежит языку, ни один доказывающий, даже злонамеренный, не сможет убедить проверяющего принять строку с вероятностью, превышающей 1/3. Такая машина потенциально мощнее обычного протокола взаимодействия NP, а проверка доказательств не менее практична, поскольку алгоритмы BPP рассматриваются как абстракция практических вычислений (см. BPP).

Общественный протокол монеты против частного протокола монеты

В протоколе с открытыми монетами случайные выборы, сделанные верификатором, становятся общедоступными. Они остаются приватными в протоколе с закрытыми монетами. На той же конференции, где Бабаи определил свою систему доказательств для MA, Шафи Голдвассер, Сильвио Микали и Чарльз Рэккофф опубликовали статью, определяющую интерактивную систему доказательств IP[f(n)]. Она использует те же машины, что и протокол MA, за исключением того, что допускается f(n) раундов для входных данных размера n. В каждом раунде верификатор выполняет вычисления и передает сообщение проверяющему, а проверяющий выполняет вычисления и передает информацию обратно верификатору. В конце верификатор должен принять решение. Например, в протоколе IP[3] последовательность будет VPVPVPV, где V – ход верификатора, а P – ход проверяющего. В протоколах Артура–Мерлина Бабаи определил аналогичный класс AM[f(n)], который допускал f(n) раундов, но наложил одно дополнительное условие на машину: верификатор должен показать проверяющему все случайные биты, которые он использует в своих вычислениях. В результате верификатор не может "скрыть" ничего от проверяющего, поскольку проверяющий достаточно силен, чтобы имитировать все действия верификатора, если он знает, какие случайные биты были использованы. Это называется протоколом с открытыми монетами, потому что случайные биты ("подбрасывания монеты") видны обеим машинам. Подход IP, напротив, называется протоколом с закрытыми монетами. Существенная проблема с открытыми монетами заключается в том, что если проверяющий злонамеренно пытается убедить верификатора принять строку, не принадлежащую языку, то верификатор, возможно, сможет сорвать его планы, если сможет скрыть свое внутреннее состояние. Это было основной мотивацией для определения систем доказательств IP. В 1986 году Голдвассер и Сипсер, возможно, к удивлению, показали, что способность верификатора скрывать подбрасывания монеты от проверяющего мало что дает, поскольку протокол Артура–Мерлина с открытыми монетами, содержащий всего на два раунда больше, может распознавать все те же языки. В результате протоколы с открытыми и закрытыми монетами примерно эквивалентны. Фактически, как показал Бабаи в 1988 году, AM[k]=AM для всех констант k, поэтому IP[k] не имеют преимуществ перед AM. Чтобы продемонстрировать мощь этих классов, рассмотрим проблему изоморфизма графов – задачу определения, можно ли переставить вершины одного графа так, чтобы он стал идентичным другому графу. Эта задача находится в NP, поскольку доказательством является перестановка, делающая графы равными. Оказывается, что дополнение к проблеме изоморфизма графов, задача co-NP, о которой неизвестно, что она принадлежит NP, имеет алгоритм AM, и лучше всего это увидеть через алгоритм с закрытыми монетами.

ИП

Частные монеты могут оказаться бесполезными, но большее количество раундов взаимодействия – полезно. Если мы позволим вероятностному проверяющему и всемогущему доказывающему взаимодействовать в течение полиномиального числа раундов, мы получим класс задач, называемый IP. В 1992 году Ади Шамир установил в одном из центральных результатов теории сложности, что IP равен PSPACE, классу задач, разрешимых обычной детерминированной машиной Тьюринга за полиномиальное пространство.

QIP

Если мы позволим элементам системы использовать квантовые вычисления, то такая система называется квантовой интерактивной системой доказательств, а соответствующий класс сложности — QIP. Серия результатов завершилась прорывом в 2010 году, установившим равенство QIP = PSPACE.

Нулевое знание

Не только интерактивные системы доказательств способны решать задачи, которые, как считается, не принадлежат классу NP, но при допущении существования односторонних функций, доказывающий может убедить проверяющего в правильности решения, не раскрывая при этом никакой информации о самом решении. Это особенно важно, когда проверяющему нельзя доверять полное решение. На первый взгляд кажется невозможным убедить проверяющего в существовании решения, не предъявив ему никакого доказательства, однако такие доказательства, известные как доказательства с нулевым разглашением, предположительно существуют для всех задач из класса NP и представляют ценность в криптографии. Доказательства с нулевым разглашением впервые были описаны в основополагающей работе 1985 года по интерактивным системам доказательств Голдвассером, Микали и Рэккоффом для конкретных задач теории чисел. Однако истинный потенциал этих доказательств был продемонстрирован Одедом Голдрейхом, Сильвио Микали и Ави Вигдерсоном.

МДП

Одной из целей разработчиков IP было создание максимально мощной интерактивной системы доказательств, и поначалу кажется, что её нельзя сделать мощнее, не увеличив вычислительные возможности верификатора и не сделав его непрактичным. Голдвассер и др. преодолели это ограничение в своей работе 1988 года «Многопроверные интерактивные доказательства: как избавиться от предположений о вычислительной сложности», в которой определяется вариант IP, называемый MIP, использующий двух независимых доказывающих. Эти два доказывающих не могут общаться после того, как верификатор начнет отправлять им сообщения. Подобно тому, как легче определить, лжет ли преступник, если его и его сообщника допрашивают в разных комнатах, значительно проще обнаружить злоумышленника, пытающегося обмануть верификатора и заставить его принять строку, не принадлежащую языку, если есть другой доказывающий, с которым можно перепроверить. Этот факт оказался настолько полезным, что Бабаи, Фортноу и Лунд доказали, что MIP = NEXPTIME – класс всех задач, разрешимых недетерминированной машиной за экспоненциальное время, что является очень широким классом. NEXPTIME включает в себя PSPACE, и предполагается, что он строго включает PSPACE. Добавление любого фиксированного числа дополнительных доказывающих сверх двух не позволяет распознавать больше языков. Этот результат подготовил почву для знаменитой теоремы PCP, которую можно рассматривать как «масштабированную» версию этой теоремы. MIP также обладает полезным свойством: доказательства с нулевым разглашением для любого языка из NP можно описать без предположений об односторонних функциях, необходимых для IP. Это важно при разработке криптографических алгоритмов, устойчивых к взлому по определению.

ПКП

В то время как разработчики интерактивных доказательств рассматривали обобщения интерактивных систем доказательств Бабая, другие изучали ограничения. Очень полезной интерактивной системой доказательств является PCP(f(n), g(n)), которая является ограничением класса MA, где Артур может использовать только f(n) случайных битов и может просматривать только g(n) битов сертификата доказательства, отправленного Мерлином (фактически, используя произвольный доступ). Существует ряд легко доказуемых результатов о различных классах PCP. 1 = PCP(0, poly), класс машин полиномиального времени без случайности, но с доступом к сертификату, является просто NP. 1 = PCP(poly, 0), класс машин полиномиального времени с доступом к полиномиальному числу случайных битов, является co-RP. Первым важным результатом Ароры и Сафры было то, что; другими словами, если верификатор в протоколе NP вынужден выбирать только O(log n) битов сертификата доказательства для проверки, это не имеет значения, если у него есть O(log n) случайных битов для использования. Более того, теорема PCP утверждает, что число обращений к доказательству можно уменьшить до константы. То есть, 1 = NP = PCP(log, O(1)). Они использовали эту ценную характеристику NP, чтобы доказать, что алгоритмы приближения не существуют для задач оптимизации некоторых NP-полных задач, если P ≠ NP. Такие задачи сейчас изучаются в области, известной как сложность приближения.

Учебники

Арора, Санджиев; Барак, Боаз, "Теория сложности: современный подход", Cambridge University Press, март 2009 года. Раздел 10.4: Интерактивные системы доказательств, с. 354–366. Раздел 19.2: Игры против природы и интерактивные протоколы, с. 469–480.