Из Википедии, свободной энциклопедии
  (Перенаправлено из интерактивных систем проверки )
Перейти к навигации Перейти к поиску
Не путать с помощником Proof .
Общее представление протокола интерактивного доказательства.

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

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

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

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

НП [ править ]

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

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

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

Протоколы Артура-Мерлина и Мерлина-Артура [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

IP [ править ]

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

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

QIP [ править ]

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

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

Нулевое знание [ править ]

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

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

MIP [ править ]

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

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

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

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

PCP [ править ]

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

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

Существует ряд легко подтверждаемых результатов о различных классах PCP . , класс машин с полиномиальным временем без случайности, но с доступом к сертификату, - это просто NP . , класс машин с полиномиальным временем с доступом к полиномиально множеству случайных битов - это co- RP . Первым важным результатом Ароры и Сафры было то, что PCP (log, log) = NP ; Другими словами, если проверяющий в протоколе NP ограничен выбирать только биты проверочного сертификата для просмотра, это не будет иметь никакого значения, если у него есть случайные биты для использования. [13]

Кроме того, теорема PCP утверждает, что количество обращений к доказательству может быть сведено к константе. То есть . [14] Они использовали эту ценную характеристику NP, чтобы доказать, что алгоритмы аппроксимации не существуют для оптимизационных версий некоторых NP-полных задач, если P = NP . Такие проблемы сейчас изучаются в области, известной как трудность приближения .

См. Также [ править ]

  • Машина Oracle

Ссылки [ править ]

  1. ^ Ласло Бабай. Теория торговых групп для случайности . Труды семнадцатого ежегодного симпозиума по теории вычислений , ACM. 1985 г.
  2. ^ Goldwasser, S .; Micali, S .; Ракофф, К. (1989). «Сложность знаний интерактивных систем доказательства» (PDF) . SIAM Journal on Computing . 18 (1): 186–208. DOI : 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 [ квант-ф ].
  8. ^ Джайн, Рахул; Цзи, Чжэнфэн; Упадхьяй, Сарвагья; Уотроус, Джон (2010). «QIP = PSPACE». STOC '10: Материалы 42-го симпозиума ACM по теории вычислений . ACM. С. 573–582. ISBN 978-1-4503-0050-6.
  9. Перейти ↑ Aaronson, S. (2010). «QIP = прорыв PSPACE». Коммуникации ACM . 53 (12): 101. DOI : 10,1145 / 1859204,1859230 .
  10. ^ a b М. Бен-ор, Шафи Гольдвассер, Дж. Килиан и А. Вигдерсон. Интерактивные доказательства с несколькими доказательствами: как удалить предположения о неразрешимости . Труды 20-го симпозиума ACM по теории вычислений , стр. 113–121. 1988 г.
  11. ^ Ласло Бабай, Л. Fortnow и С. Лунд. Недетерминированное экспоненциальное время имеет интерактивные протоколы с двумя проверяющими . Вычислительная сложность , том 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 [полилог] , coAM , BP • NP
    • QMA , QMA + , QMA (2) , журнал QMA , QMAM
    • IP , MIP , IPP , QIP , QIP (2) , compIP , frIP
    • PCP (r (n), q (n))
  • Ларри Гоник. « Доказательство положительного? ». Комикс об интерактивных системах доказательства.