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

Не путать с Помощник доказательства.

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

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

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

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

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

НП

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

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

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

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

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

Хотя NP можно рассматривать как использование взаимодействия, только в 1985 году концепция вычислений посредством взаимодействия была задумана (в контексте теории сложности) двумя независимыми группами исследователей. Один подход, автор Ласло Бабай, опубликовавший "Теорию торговых групп для случайности",^[1] определил Артур-Мерлин (AM) иерархия классов. В этой презентации Артур (проверяющий) является вероятностный, машина с полиномиальным временем, в то время как Мерлин (доказывающий) имеет неограниченные ресурсы.

Класс MA в частности, это простое обобщение описанного выше взаимодействия NP, в котором верификатор является вероятностным, а не детерминированным. Кроме того, вместо того, чтобы требовать, чтобы верификатор всегда принимал действительные сертификаты и отклонял недействительные сертификаты, он является более снисходительным:

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

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

Протокол публичных монет против протокола приватных монет

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

На той же конференции, где Бабай определил свою систему доказательства для MA, Шафи Гольдвассер, Сильвио Микали и Чарльз Ракофф^[2] опубликовал документ, определяющий систему интерактивных доказательств IP[ж(п)]. Это те же машины, что и MA протокол, за исключением того ж(п) раунды допускаются для ввода размера п. В каждом раунде верификатор выполняет вычисления и передает сообщение доказывающему, а доказывающий выполняет вычисления и передает информацию обратно верификатору. В конце верификатор должен принять решение. Например, в IP[3], последовательность будет VPVPVPV, где V - ход проверяющего, а P - ход проверяющего.

В протоколах Артура-Мерлина Бабай определил аналогичный класс AM[ж(п)], что позволило ж(п), но он наложил на машину одно дополнительное условие: проверяющий должен показать доказывающему все случайные биты, которые он использует в своих вычислениях. В результате проверяющий не может «скрыть» что-либо от проверяющего, потому что доказывающий достаточно силен, чтобы моделировать все, что делает проверяющий, если он знает, какие случайные биты он использовал. Это называется общественная монета протокол, потому что случайные биты («подбрасывание монеты») видны обеим машинам. В IP подход называется частная монета протокол, напротив.

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

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

Чтобы продемонстрировать мощь этих классов, рассмотрим проблема изоморфизма графов, проблема определения, можно ли переставить вершины одного графа так, чтобы он был идентичен другому графу. Эта проблема в НП, поскольку сертификат доказательства - это перестановка, которая уравнивает графики. Получается, что дополнять проблемы изоморфизма графов,НП проблема неизвестна в НП, имеет AM алгоритм и лучший способ увидеть это через алгоритм частных монет.^[5]

IP

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

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

QIP

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

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

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

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

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

MIP

Одна цель IP 'Разработчики должны были создать максимально мощную интерактивную систему доказательств, и сначала казалось, что ее нельзя сделать более мощной, не сделав верификатор более мощным и непрактичным. Goldwasser et al. преодолели это в своих «Интерактивных доказательствах с множеством доказательств: как удалить допущения о неразрешимости» 1988 года, в которых определяется вариант IP называется MIP в котором есть два независимые испытатели.^[10] Два проверяющих не могут общаться, если проверяющий начал посылать им сообщения. Так же, как легче определить, лжет ли преступник, если его и его партнера допрашивают в разных комнатах, значительно проще обнаружить злонамеренного доказывающего, пытающегося обмануть проверяющего, чтобы он принял строку не на языке, если есть другой доказывающий, который может перепроверьте с.

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

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

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

PCP

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

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

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

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

Смотрите также

• Машина Oracle

использованная литература

1. Ласло Бабай. Теория торговых групп для случайности. Труды семнадцатого ежегодного симпозиума по теории вычислений, ACM. 1985 г.
2. Goldwasser, S .; Micali, S .; Ракофф, К. (1989). «Сложность знаний интерактивных систем доказательства» (PDF). SIAM Журнал по вычислениям. 18 (1): 186–208. Дои:10.1137/0218012. ISSN  1095-7111. Расширенная аннотация
3. Шафи Гольдвассер и Майкл Сипсер. Частные монеты против публичных монет в интерактивных системах проверки. Материалы ACM STOC'86С. 58–68. 1986 г.
4. Ласло Бабай и Шломо Моран. Игры Артура – ​​Мерлина: рандомизированная система доказательств и иерархия классов сложности. Журнал компьютерных и системных наук, 36: с.254–276. 1988 г.
5. О. Гольдрайх, С. Микали, А. Вигдерсон. Доказательства, которые не дают ничего, кроме их достоверности. Журнал ACM, том 38, выпуск 3, с.690–728. Июль 1991 г.
6. Ади Шамир. IP = PSPACE. Журнал ACM, том 39, выпуск 4, с.869–877. Октябрь 1992 г.
7. Цуёси Ито; Хиротада Кобаяши; Джон Уотроус (2010). «Квантовые интерактивные доказательства со слабыми границами ошибок». arXiv:1012.4427v2 [Quant-ph ].
8. Джайн, Рахул; Цзи, Чжэнфэн; Упадхьяй, Сарвагья; Уотроус, Джон (2010). «QIP = PSPACE». STOC '10: Материалы 42-го симпозиума ACM по теории вычислений. ACM. С. 573–582. ISBN  978-1-4503-0050-6.
9. Ааронсон, С. (2010). «QIP = прорыв PSPACE». Коммуникации ACM. 53 (12): 101. Дои:10.1145/1859204.1859230.
10. М. Бен-ор, Шафи Гольдвассер, Дж. Килиан и А. Вигдерсон. Интерактивные доказательства с несколькими доказательствами: как удалить предположения о неразрешимости. Материалы 20-го симпозиума ACM по теории вычисленийС. 113–121. 1988 г.
11. Ласло Бабай, Л. Фортноу и К. Лунд. Недетерминированное экспоненциальное время имеет интерактивные протоколы с двумя проверяющими. Вычислительная сложность, том 1, стр. 3–40. 1991 г.
12. http://groups.csail.mit.edu/cis/pubs/shafi/1988-stoc-bgkw.pdf
13. Санджив Арора и Шмуэль Сафра. Вероятностная проверка доказательств: новая характеристика NP. Журнал ACM, том 45, выпуск 1, стр. 70–122. Январь 1998 г.
14. Санджив Арора, К. Лунд, Р. Мотвани, М. Судан и М. Сегеди. Проверка доказательства и трудность аппроксимационных задач.. Материалы 33-го симпозиума IEEE по основам информатики, стр. 13–22. 1992 г.

Учебники

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

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

• Декстер Козен. Интерактивные доказательства. CS682 Spring 2004 конспект лекций. Департамент компьютерных наук Корнельского университета.
• Зоопарк сложности:
  • MA, MA ', MAEXP, MAE
  • AM, AMEXP, AM пересекаются со-AM, AM [полилог], коАМ, БП • НП
  • QMA, QMA +, QMA (2), QMA_журнал, QMAM
  • IP, MIP, IPP, QIP, QIP (2), compIP, frIP
  • PCP (r (n), q (n))
• Ларри Гоник. "Доказательство положительное? Комикс про интерактивные системы проверки.