Войти
Общее представление протокола интерактивной проверки. В теория вычислительной сложности, интерактивная система доказательства - это абстрактная машина, которая моделирует вычисление как обмен сообщениями между двумя сторонами: доказывающим и верификатор. Стороны взаимодействуют путем обмена сообщениями, чтобы установить, принадлежит ли данная строка к языку или нет. Доказывающий всесилен и обладает неограниченными вычислительными ресурсами, но ему нельзя доверять, в то время как верификатор имеет ограниченные вычислительные мощности. Сообщения отправляются между проверяющим и доказывающим до тех пор, пока проверяющий не получит ответ на проблему и не «убедит» себя в его правильности.
Все интерактивные системы доказательства предъявляют два требования:
Предполагается, что проверяющий всегда честен.
Конкретный характер системы и, следовательно, класс сложности языков, которые она может распознать, зависят от того, какие ограничения накладываются на верификатор, а также от того, какие возможности ему даются. - например, большинство интерактивных систем доказательства критически зависят от способности проверяющего делать случайный выбор. Это также зависит от характера передаваемых сообщений - сколько и что они могут содержать. Было обнаружено, что интерактивные системы доказательств имеют некоторые важные последствия для традиционных классов сложности, определенных с использованием только одной машины. Основными классами сложности, описывающими интерактивные системы проверки, являются AM и IP.
Класс сложности NP можно рассматривать как очень простую систему доказательств. В этой системе верификатор представляет собой детерминированную машину полиномиального времени (машина P ). Протокол:
В случае, когда существует действительный подтверждающий сертификат, доказывающая сторона всегда может заставить проверяющую принять его, предоставив ему этот сертификат. Однако в случае отсутствия действительного подтверждающего сертификата ввод не на языке, и никакой доказывающий, каким бы злонамеренным он ни был, не может убедить проверяющего в обратном, потому что любой подтверждающий сертификат будет отклонен.
Хотя NP можно рассматривать как использующее взаимодействие, концепция вычислений посредством взаимодействия возникла только в 1985 году (в контексте сложности теория) двумя независимыми группами исследователей. Один из подходов, разработанный Ласло Бабай, опубликовавший «Теорию торговых групп для случайности», определил иерархию классов Артура-Мерлина (AM ). В этой презентации Артур (проверяющий) - это вероятностная машина полиномиального времени, в то время как Мерлин (доказывающий) имеет неограниченные ресурсы.
Класс MA, в частности, является простым обобщением описанного выше взаимодействия NP, в котором проверяющий является вероятностным, а не детерминированным. Кроме того, вместо того, чтобы требовать, чтобы верификатор всегда принимал действительные сертификаты и отклонял недействительные сертификаты, он более снисходительный:
Эта машина потенциально более мощная, чем обычный протокол взаимодействия NP , и сертификаты не менее практичны для проверки, поскольку BPP алгоритмы рассматриваются как абстрактные практические вычисления (см. BPP ).
В протоколе публичных монет случайные выборы, сделанные проверяющим, становятся общедоступными. Они остаются закрытыми в частном протоколе монет.
На той же конференции, где Бабай определил свою систему доказательств для MA, Шафи Голдвассера, Сильвио Микали и Чарльз Рэкофф опубликовал статью, определяющую интерактивное доказательство. система IP [f (n)]. Он имеет те же машины, что и протокол MA, за исключением того, что для ввода размера n разрешены раунды f (n). В каждом раунде верификатор выполняет вычисление и передает сообщение доказывающему, а доказывающий выполняет вычисления и передает информацию обратно проверяющему. В конце верификатор должен принять решение. Например, в протоколе IP [3] последовательность будет VPVPVPV, где V - ход проверяющего, а P - ход проверяющего.
В протоколах Артура-Мерлина Бабай определил аналогичный класс AM [f (n)], который допускал f (n) раундов, но он наложил на машину одно дополнительное условие: верификатор должен показать доказывающему все случайные биты, которые он использует в своих вычислениях. В результате проверяющий не может «спрятать» что-либо от проверяющего, поскольку доказывающий достаточно силен, чтобы моделировать все, что делает проверяющий, если он знает, какие случайные биты он использовал. Это называется протоколом публичных монет, потому что случайные биты («подбрасывания монет») видны обеим машинам. Напротив, подход IP называется протоколом частных монет.
Существенная проблема с общедоступными монетами заключается в том, что если проверяющий желает злонамеренно убедить проверяющего принять строку не на языке, похоже, что проверяющий может помешать своим планам, если сможет скрыть его внутреннее состояние от него. Это было основным мотивом при определении систем защиты IP .
В 1986 году Голдвассер и Сипсер показали, что, возможно, удивительно, что способность проверяющего скрывать подбрасывание монеты от проверяющего, в конце концов, мало помогает в том, что протокол публичных монет Артура-Мерлина с помощью еще двух раундов можно распознавать все те же языки. В результате протоколы публичных и частных монет примерно эквивалентны. Фактически, как показывает Бабай в 1988 году, AM [k] = AM для всех констант k, поэтому IP [k] не имеет преимущества перед AM.
Чтобы продемонстрировать мощь этих классов, рассмотрим проблему изоморфизма графов, проблему определения, можно ли переставить вершины одного графа так, чтобы он был идентичен другому графу. Эта проблема находится в NP, поскольку сертификат доказательства - это перестановка, которая делает графики равными. Оказывается, что дополнение проблемы изоморфизма графов, проблема со- NP, о которой не известно в NP, имеет AM, и лучший способ увидеть это - использовать алгоритм частных монет.
Частные монеты могут быть бесполезны, но полезны дополнительные раунды взаимодействия. Если мы позволим машине вероятностного верификатора и всемогущей доказывающей стороне взаимодействовать в течение полиномиального числа раундов, мы получим класс проблем, называемый IP . В 1992 году Ади Шамир обнаружил в одном из центральных результатов теории сложности, что IP равно PSPACE, классу задач, решаемых с помощью обычная детерминированная машина Тьюринга в полиномиальном пространстве.
Если мы позволим элементам системы использовать квантовые вычисления, система будет называется квантовой интерактивной системой доказательства, а соответствующий класс сложности называется QIP . Серия результатов завершилась прорывом в 2010 году, который показал, что QIP = PSPACE .
Не только интерактивные системы доказательства могут решать проблемы, которые, как считается, не входят в NP., но при предположении о существовании односторонних функций доказывающая сторона может убедить проверяющую в решении, даже не сообщая проверяющей информации о решении. Это важно, когда верификатору нельзя доверять полное решение. Поначалу кажется невозможным, чтобы верификатор мог быть убежден в существовании решения, если верификатор не видел сертификата, но такие доказательства, известные как доказательства с нулевым разглашением, на самом деле считаются существующими для всех проблем. в НП и ценны в криптографии. Доказательства с нулевым разглашением были впервые упомянуты в оригинальной статье 1985 года о IP Голдвассером, Микали и Ракоффом, но степень их силы была показана Одедом Голдрайхом, Сильвио Микали. и Avi Wigderson.
Одной из целей дизайнеров IP было создание самой мощной из возможных интерактивных систем проверки, и поначалу казалось, что это невозможно сделать более мощным, не сделав верификатор более мощным и непрактичным. Goldwasser et al. преодолели это в своих «Интерактивных доказательствах с несколькими доказывающими устройствами: как удалить допущения о неразрешимости» 1988 года, в которых определяется вариант IP, называемый MIP, в котором есть два независимых доказывающих. Два доказывающих не могут обмениваться данными после того, как проверяющий начал отправлять им сообщения. Так же, как легче определить, лжет ли преступник, если его и его партнера допрашивают в разных комнатах, значительно проще обнаружить злонамеренного доказывающего, пытающегося обмануть проверяющего, чтобы он принял строку не на языке, если есть другой доказывающий, который может перепроверьте с.
Фактически, это настолько полезно, что Бабай, Фортноу и Лунд смогли показать, что MIP= NEXPTIME, класс всех проблем, решаемых с помощью недетерминированная машина в экспоненциальном времени, очень большой класс. NEXPTIME содержит PSPACE и, как полагают, строго содержит PSPACE. Добавление постоянного числа дополнительных испытателей сверх двух не позволяет распознавать какие-либо языки. Этот результат проложил путь к знаменитой теореме PCP, которую можно рассматривать как "уменьшенную" версию этой теоремы.
MIP также имеет полезное свойство, заключающееся в том, что доказательства с нулевым разглашением для каждого языка в NP могут быть описаны без предположения об односторонних функциях, которые должен выполнять IP . Это имеет отношение к разработке доказуемо нерушимых криптографических алгоритмов. Более того, протокол MIP может распознавать все языки в IP только за постоянное количество раундов, а если добавлен третий доказывающий, он может распознавать все языки в NEXPTIME за постоянное количество раундов, снова демонстрируя свою мощь над IP.
. Известно, что для любого постоянного k система MIP с k доказывающими и полиномиально большим количеством раундов может быть превращена в эквивалентную систему только с 2 доказывающими и постоянное количество патронов.
В то время как разработчики IP рассматривали обобщения интерактивных систем доказательства Бабая, другие рассматривали ограничения. Очень полезной интерактивной системой проверки является PCP (f (n), g (n)), которая является ограничением MA, где Артур может использовать только случайные биты f (n) и может проверять только g (n) битов сертификата подтверждения, отправленного Мерлином (по существу, используя произвольный доступ ).
Существует ряд легко подтверждаемых результатов о различных классах PCP . 
Кроме того, теорема PCP утверждает, что количество попыток доступа может быть полностью уменьшено до константы. То есть 
