Введение

В теории вычислительной сложности класс IP (интерактивное доказательство) — это класс задач, разрешимых с помощью интерактивной системы доказательств. Он равен классу PSPACE. Этот результат был установлен в серии работ: первая, выполненная Лундом, Карлоффом, Фортноу и Нисаном, показала, что co NP имеет интерактивные доказательства с несколькими участниками; а вторая, предложенная Шамиром, использовала их технику для установления равенства IP = PSPACE. Этот результат является известным примером, когда доказательство не релятивизируется. Концепция интерактивной системы доказательств была впервые представлена Шафи Голдвассером, Сильвио Микали и Чарльзом Рэккоффом в 1985 году. Интерактивная система доказательств состоит из двух машин: доказывающего, P, который предоставляет доказательство того, что данная строка n принадлежит некоторому языку, и проверяющего, V, который удостоверяется в корректности представленного доказательства. Предполагается, что доказывающий обладает неограниченными вычислительными ресурсами и памятью, в то время как проверяющий является вероятностной машиной с полиномиальным временем работы и доступом к случайной битовой строке, длина которой полиномиально зависит от размера n. Эти две машины обмениваются полиномиальным количеством сообщений, p(n), и после завершения взаимодействия проверяющий должен решить, принадлежит ли n данному языку, с вероятностью ошибки не более 1/3. (Следовательно, любой язык из класса BPP принадлежит классу IP, поскольку в этом случае проверяющий может просто игнорировать доказывающего и принимать решение самостоятельно.)

Доказательство IP = PSPACE

Доказательство можно разделить на две части: мы показываем, что IP ⊆ PSPACE и PSPACE ⊆ IP.

PSPACE IP

Для иллюстрации техники, которая будет использована для доказательства PSPACE ⊆ IP, мы сначала докажем более слабую теорему, доказанную Лундом и другими авторами: #SAT ∈ IP. Затем, используя концепции из этого доказательства, мы расширим его, чтобы показать, что TQBF ∈ IP. Поскольку TQBF является PSPACE-полной задачей, а TQBF ∈ IP, то PSPACE ⊆ IP.

Варианты

Существует несколько вариантов интерактивных доказательств, незначительно модифицирующих определение интерактивной системы доказательств. Мы приведем здесь некоторые из наиболее известных.

dIP

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

МДП

В 1988 году Голдвассер и др. создали еще более мощную интерактивную систему доказательств, основанную на IP, под названием MIP, в которой участвуют два независимых доказывающих. Эти два доказывающих не могут общаться после того, как верификатор начал отправлять им сообщения. Подобно тому, как легче распознать ложь преступника, если его и его сообщника допрашивают раздельно, значительно проще обнаружить злоумышленника, пытающегося обмануть верификатора, если есть другой доказывающий, с которым можно перепроверить информацию. Этот факт оказался настолько полезным, что Бабаи, Фортноу и Лунд доказали, что MIP = NEXPTIME – класс всех задач, разрешимых недетерминированной машиной за экспоненциальное время, что является очень широким классом. Более того, для всех языков из NP существуют доказательства с нулевым разглашением в системе MIP без каких-либо дополнительных предположений; для IP это известно лишь при условии существования односторонних функций.

ИПП

IPP (unbounded IP) — это вариант IP, в котором верификатор BPP заменяется верификатором PP. Более точно, условия полноты и надёжности модифицируются следующим образом:

Полнота: если строка принадлежит языку, честный верификатор будет убеждён в этом честным доказывающим с вероятностью не менее 1/2. Надёжность: если строка не принадлежит языку, ни один доказывающий не сможет убедить честного верификатора в том, что она принадлежит языку, за исключением случая, когда вероятность этого меньше 1/2. Хотя IPP также эквивалентен PSPACE, протоколы IPP ведут себя существенно иначе, чем IP, применительно к оракулам: IPP=PSPACE для всех оракулов, в то время как IP ≠ PSPACE для почти всех оракулов.

QIP

QIP — это версия IP, в которой верификатор BPP заменен верификатором BQP, где BQP — класс задач, разрешимых квантовыми компьютерами за полиномиальное время. Сообщения состоят из кубитов. В 2009 году Джейн, Джи, Упадхьяя и Ватрус доказали, что QIP также равен PSPACE, что означает, что данное изменение не придает протоколу дополнительных возможностей. Это включает в себя более ранний результат Китаева и Ватруса о том, что QIP содержится в EXPTIME, поскольку QIP = QIP[3], а значит, более трех раундов никогда не требуется.