Квантовые вычисления со времен Демокрита - Скотт Ааронсон

но ненадежный доказывающий маг, — снабжает нас сертификатом полиномиального размера, а затем «Артур» — скептически настроенный король полиномиального времени — запускает рандомизированный алгоритм для проверки мерлинова сертификата. Более формально MA можно определить как класс языков L, для которых существует рандомизированный алгоритм полиномиального времени V для Мерлина, такой, что для любого x:

1. Если x ∈ L, то существует по крайней мере один сертификат w, такой, что V(x, w) принимает наверняка.

2. Если x ∉ L, то, вне зависимости от w, V(x, w) отвергает с вероятностью по крайней мере 1/2.

Оказывается, если заменить в пункте 1 «наверняка» на «с вероятностью не менее 2/3», то получится в точности тот же класс MA. (Доказательство этого занимает страницу-другую, поэтому мы не будем здесь его приводить.) Можно показать также, что NP и BPP содержатся в MA и что MA содержится в PP и Σ2P ∩ П2P.

Теперь, когда у нас появились персонажи Мерлин и Артур, мы можем определить также и более интересные игры. В частности, предположим, что Артур должен послать Мерлину случайный вызов, на который тот должен ответить. Тогда вы получаете новый класс под названием AM («Артур — Мерлин»), который содержит в себе MA, но не факт, что совпадает с ним и, в свою очередь, содержится в П2P. На самом деле должен сказать, что большинство из нас сегодня предполагают, что NP = MA = AM; в самом деле, известно, что это следует из гипотезы о нижней оценке сложности схемы — аналогично тому, как утверждается равенство P = BPP (см. главу 7). Но пока мы очень далеки от возможности доказать это.

Вы можете задаться вопросом: что происходит, если после получения ответа от Мерлина Артур задает Мерлину следующий вопрос или три-четыре следующих вопроса? Можно подумать, что в этом случае Мерлин смог бы доказать Артуру даже больше, верно? Неверно! Еще одна удивительная теорема гласит, что AM = AMAM = AMAMAM…, то есть любое фиксированное число вопросов Мерлину имеет ровно ту же силу, что и один вопрос.

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

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

Интуитивно это представляется невозможным, но я проиллюстрирую на примере. Предположим, у нас имеется два графа. Если они изоморфны, то доказать это легко. Но предположим, они не изоморфны. Как доказать это кому-то, если представить, что вы — всемогущий маг?

Очень просто: предложите человеку, которого вы пытаетесь убедить, выбрать один из двух графов случайным образом, затем случайно его преобразовать и переслать вам то, что получилось. И пусть затем этот человек спросит: «С каким графом я работал?» Если два графа не были изоморфны, то вы должны быть в состоянии уверенно ответить на этот вопрос. В противном случае вы сможете ответить на него только с вероятностью 1/2. Таким образом, вы почти наверняка ошибетесь, если этот тест будет повторен некоторое небольшое число раз.

Это пример интерактивной доказательной системы. Делаем ли мы при этом какие-то допущения? Мы предполагаем, что вы не знаете, с какого именно графа начинал проверяющий, и не имеете прямого доступа к его мозгу, то есть не можете определить это непосредственно. Или, как сказали бы специалисты по теоретической информатике, мы предполагаем, что вы не имеете доступа к «частным случайным битам» проверяющего.

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

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

При определенном вычислительном допущении, а именно что односторонние функции существуют, можно показать, что доказательства с нулевым разглашением существуют для любой NP-полной задачи. Именно такое замечательное открытие сделали Голдрейх, Микали и Вигдерсон в 1986 г.[100]

Поскольку все NP-полные задачи сводятся одна к другой (то есть представляют собой «одну и ту же задачу в разных обличьях»), достаточно привести протокол с нулевым разглашением для одной NP-полной задачи. И оказывается, что удобно выбрать для этой цели задачу раскраски графа в три цвета, в которой каждый узел графа окрашивается в красный, синий или зеленый цвет так, чтобы никакие два соседние узла не оказались одного цвета. У вас в руках черно-белая книга, но вы можете воспользоваться своим воображением и представить, что в изображенном на рисунке-графе имеется по два узла каждого цвета — красных, синих и зеленых.

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

А вот как. Если наш граф раскрашен в три цвета, то сначала мы случайным образом переставим цвета: к примеру, заменим все синие области на зеленые, все зеленые на красные, а все красные на синие. (Существует 3! = 6 возможных перестановок.) Затем пошлем проверяющему зашифрованные сообщения, в которых будут закодированы все цвета — это, по существу, обеспечит «цифровую привязку» вас к этим цветам. Говоря более подробно, эти сообщения должны обладать следующими свойствами:

1. Проверяющий не может прочесть их (то есть взлом шифра вычислительно невозможен), но

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

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