Интерактивная система доказательств

Не путать с Proof Assistant .

Общее представление протокола интерактивного доказательства.

В теории сложности вычислений интерактивная система доказательства — это абстрактная машина , которая моделирует вычисления как обмен сообщениями между двумя сторонами: доказывающим и проверяющим . Стороны взаимодействуют путем обмена сообщениями, чтобы выяснить, ли данная строка принадлежит языку или нет. Доказывающее обладает неограниченными вычислительными ресурсами, но ему нельзя доверять, в то время как верификатор имеет ограниченную вычислительную мощность, но считается всегда честным. Сообщения передаются между проверяющим и проверяющим до тех пор, пока проверяющий не получит ответ на проблему и не «убедит» себя в его правильности.

Ко всем интерактивным системам доказательства предъявляются два требования:

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

Конкретная природа системы и, следовательно, класс сложности языков, которые она может распознать, зависят от того, какие ограничения наложены на проверяющего, а также от того, какие способности ему предоставлены - например, большинство интерактивных систем доказательства критически зависят от способность верификатора делать случайный выбор. Это также зависит от характера обмениваемых сообщений — сколько и что они могут содержать. Было обнаружено, что системы интерактивных доказательств имеют некоторые важные последствия для традиционных классов сложности, определяемых с использованием только одной машины. Основными классами сложности, описывающими интерактивные системы доказательств, являются AM и IP .

Фон

Каждая интерактивная система доказательства определяет формальный язык строк. $L$. Надежность системы доказательств относится к свойству, которое ни один доказывающий не может заставить проверяющего принять неверное утверждение. $y\not \in L$ разве что с некоторой небольшой вероятностью. Верхняя граница этой вероятности называется ошибкой надежности системы доказательства. Более формально, для каждого доказывающего $({\tilde {\mathcal {P}}})$и каждый $y\not \in L$:

$\Pr[(\perp ,({\text{accept}}))\gets ({\tilde {\mathcal {P}}})(y)\leftrightarrow ({\mathcal {V}})(y)]<\epsilon .$

для некоторых $\epsilon \ll 1$.Пока ошибка достоверности ограничена полиномиальной долей потенциального времени работы верификатора (т. е. $\epsilon \leq 1/\mathrm {poly} (|y|)$), всегда можно усилить надежность до тех пор, пока ошибка достоверности не станет незначительной функцией по сравнению со временем работы верификатора. Это достигается путем повторения доказательства и принятия его только в том случае, если все доказательства подтвердятся. После $\ell$ повторы, ошибка корректности $\epsilon$ будет сокращено до $\epsilon ^{\ell }$.

Классы интерактивных доказательств

НАПРИМЕР

Класс сложности NP можно рассматривать как очень простую систему доказательств. В этой системе верификатором является детерминированная машина с полиномиальным временем ( P- машина). Протокол:

• Доказывающее устройство просматривает входные данные и вычисляет решение, используя его неограниченную мощность, и возвращает сертификат доказательства полиномиального размера.
• Верификатор проверяет, что сертификат действителен за детерминированное полиномиальное время. Если оно действительно, оно принимается; в противном случае он отклоняет.

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

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

Основная статья: Протокол Артура-Мерлина

Хотя NP можно рассматривать как использующую взаимодействие, только в 1985 году концепция вычислений посредством взаимодействия была разработана (в контексте теории сложности) двумя независимыми группами исследователей. Один из подходов, предложенный Ласло Бабаем , опубликовавшим «Теорию торговых групп для случайности», определил иерархию классов Артура-Мерлина ( 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 называется протоколом частной монеты Напротив, .

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

В 1986 году Гольдвассер и Сипсер показал, что, возможно, удивительно, что способность верификатора скрывать подбрасывание монеты от доказывающего, в конце концов, приносит мало пользы, поскольку протокол общедоступных монет Артура-Мерлина, содержащий всего два дополнительных раунда, может распознавать все те же языки. В результате протоколы общедоступных и частных монет примерно эквивалентны. Фактически, как показал Бабай в 1988 году, AM [ k ] = AM для всех констант k , поэтому IP [ k ] не имеет преимущества перед AM .

Чтобы продемонстрировать мощь этих классов, рассмотрим проблему изоморфизма графов , проблему определения, можно ли переставить вершины одного графа так, чтобы он был идентичен другому графу. Эта проблема находится в NP , поскольку сертификат доказательства — это перестановка, которая делает графики равными. Оказывается, Дополнение проблемы изоморфизма графов, проблема co- NP , о которой не известно, что она находится в NP , имеет алгоритм AM , и лучший способ увидеть это - с помощью алгоритма частных монет.

ИП

Основная статья: IP (сложность)

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

QIP

Основная статья: QIP (сложность)

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

Ноль знаний

Основная статья: Доказательство с нулевым разглашением

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

МИП

Одной из целей разработчиков IP было создание максимально мощной интерактивной системы доказательств, и на первый взгляд кажется, что ее невозможно сделать более мощной, не сделав проверяющее устройство более мощным и непрактичным. Гольдвассер и др. преодолели это в своих «Интерактивных доказательствах с несколькими доказывающими: как устранить предположения о трудноразрешимости» 1988 года, в которых определяется вариант IP , называемый MIP , в котором есть два независимых доказывающих. Два проверяющих не могут общаться, как только проверяющий начал отправлять им сообщения. Точно так же, как легче определить, лжет ли преступник, если его и его напарника допрашивают в разных комнатах, значительно легче обнаружить злонамеренного доказывающего, пытающегося обманом заставить проверяющего принять строку, не соответствующую языку, если есть другой доказывающий, который он может перепроверьте с.

Фактически, это настолько полезно, что Бабай, Фортнов и Лунд смогли показать, что MIP = NEXPTIME , класс всех задач, решаемых недетерминированной машиной за экспоненциальное время , очень большой класс. NEXPTIME содержит PSPACE и считается, что он строго содержит PSPACE. Добавление постоянного количества дополнительных пруверов сверх двух не позволяет распознавать больше языков. Этот результат проложил путь к знаменитой теореме PCP , которую можно считать «уменьшенной» версией этой теоремы.

MIP также обладает полезным свойством: доказательства с нулевым разглашением для каждого языка в NP могут быть описаны без предположения об односторонних функциях, которые должен создавать IP . Это имеет отношение к разработке доказуемо невзламываемых криптографических алгоритмов. Более того, протокол MIP может распознавать все языки в IP только за постоянное количество раундов, а если добавить третий проверяющий, он может распознавать все языки в NEXPTIME за постоянное количество раундов, еще раз демонстрируя свою власть над IP .

Известно, что при любом постоянном k система MIP с k пруверами и полиномиальным числом раундов может быть превращена в эквивалентную систему всего с двумя пруверами и постоянным числом раундов.

PCP

Основная статья: Вероятностно проверяемое доказательство

В то время как разработчики ИС рассматривали обобщения интерактивных систем доказательств Бабая, другие рассматривали ограничения. Очень полезной интерактивной системой доказательства является PCP ( f ( n ), g ( n )), которая является ограничением MA , где Артур может использовать только f ( n ) случайных битов и может проверять только g ( n ) бит сертификата доказательства. отправлено Мерлином (по сути, с использованием произвольного доступа ).

Существует ряд легко доказуемых результатов о различных классах PCP . ⁠ ${\mathsf {PCP}}(0,{\mathsf {poly}})$⁠ класс машин с полиномиальным временем без случайности, но с доступом к сертификату, это просто NP . ⁠ ${\mathsf {PCP}}({\mathsf {poly}},0)$⁠ класс машин с полиномиальным временем и доступом к полиномиальному числу случайных битов — это co- RP . Первым крупным результатом Ароры и Сафры было то, что ⁠ ${\mathsf {PCP}}(\log ,\log )={\mathsf {NP}}$⁠ ; другими словами, если верификатор в протоколе NP вынужден выбирать только ⁠ $O(\log n)$⁠ фрагменты подтверждающего сертификата, на которые стоит посмотреть, это не будет иметь никакого значения, пока оно есть ⁠ $O(\log n)$⁠ случайные биты для использования.

Более того, теорема PCP утверждает, что количество доступов к доказательству можно свести к постоянному значению. То есть ⁠ ${\mathsf {NP}}={\mathsf {PCP}}(\log ,O(1))$⁠ . Они использовали эту ценную характеристику NP , чтобы доказать, что алгоритмов аппроксимации не существует для оптимизационных версий некоторых NP-полных задач, если только P = NP . Такие проблемы сейчас изучаются в области, известной как сложность аппроксимации .

См. также

• машина Oracle
• Доказательство знаний

Учебники

• Арора, Санджив; Барак, Боаз, «Теория сложности: современный подход» , Cambridge University Press, март 2009 г.
• Майкл Сипсер (1997). Введение в теорию вычислений . Издательство ПВС. ISBN  978-0-534-94728-6 . Раздел 10.4: Интерактивные системы доказательств, стр. 354–366.
• Христос Пападимитриу (1993). Вычислительная сложность (1-е изд.). Эддисон Уэсли. ISBN  978-0-201-53082-7 . Раздел 19.2: Игры против природы и интерактивные протоколы, стр. 469–480.

Внешние ссылки

• Декстер Козен. Интерактивные доказательства . CS682 Конспекты лекций, весна 2004 г. Департамент компьютерных наук Корнелльского университета.
• Зоопарк сложности :
  • И , И' , МАЭКСП , МАЭ
  • AM , AMEXP , AM пересекаются со-AM , AM[полилог] , coAM , BP•NP
  • QMA , QMA+ , QMA(2) , QMA _журнал , QMAM
  • IP , MIP , IPP , QIP , QIP(2) , compIP , frIP
  • PCP(r(n),q(n))
• Ларри Гоник. « Доказательство положительное? ». Комикс об интерактивных системах доказательств.