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

Некоторое время назад я беседовал с Эдом Фредкином, и он высказал уверенность в том, что вся наша Вселенная есть классический компьютер и, соответственно, все можно смоделировать классически. Но вместо того чтобы сказать далее, что квантовые вычисления невозможны, он поворачивает рассуждения в другом, очень интересном направлении и говорит, что класс BQP должен быть равен P. Хотя у нас имеются алгоритмы разложения на множители для квантовых компьютеров, более быстрые, чем известные классические алгоритмы, это не означает, что не существует быстрого классического алгоритма разложения на множители, о котором мы просто не знаем. С другой стороны, Дэвид Дойч выдвигает аргумент, о котором мы уже говорили несколько раз: если алгоритм Шора не задействует пресловутые «параллельные вселенные», то как он раскладывает число на множители?[129] Где были найдены простые делители числа, если при этом не использовалось экспоненциальное множество вселенных? Мне кажется, возразить Дойчу можно так (разумеется, это не единственное возражение): он априорно считает, что эффективной классической имитации не существует. Мы полагаем, что не существует способа, при помощи которого Природа могла бы реализовать те же вычисления при помощи полиномиальных классических средств, но точно мы этого не знаем. Доказать это мы не можем.

Почему мы не можем это доказать? Принципиальный момент в том, что если можно было бы доказать, что P ≠ BQP, то при этом было бы доказано также, что P ≠ PSPACE. Физики могут считать, что неравенство этих классов очевидно и вообще не требует доказательства, но это другой вопрос… Что до попыток пойти в обратном направлении и доказать P = BQP, то мне кажется, что такие попытки делались неоднократно. Не знаю, стоит ли говорить об этом на лекции, но я тоже посвятил этому несколько дней. По крайней мере, было бы хорошо поместить BQP в АМ или в полиномиальную иерархию — получить хотя бы предварительный результат. К несчастью, мне кажется, что мы пока просто недостаточно хорошо понимаем эффективные вычисления, чтобы отвечать на такие вопросы, даже если оставить в стороне квантовый аспект.

Вот вопрос: если P ≠ BQP, P ≠ NP и т. п., то почему никто не может доказать это? Объяснить это пытались несколькими способами. Один из них — релятивизация. Мы можем говорить о том, чтобы дать P-компьютеру и BQP-компьютеру доступ к одному и тому же оракулу. То есть снабдить их одной и той же функцией, которую они смогут вычислять за один вычислительный шаг. Тогда должен, по идее, существовать оракул, делающий их равными, и другой оракул, делающий их неравными. Роль оракула, делающего их равными, к примеру, мог бы выполнять просто PSPACE-оракул, который как бы прослаивает все и просто делает все равным PSPACE. Роль оракула, который делает их неравными, мог бы играть оракул к задаче Саймона или к какой-то задаче нахождения периода, которую квантовый компьютер решить может, а классический — нет.

Если два класса совпадают, то интуитивно непонятно, как придание большей мощности может сделать их разными? Главное здесь — понять, что когда мы снабжаем класс оракулом, мы действуем не на класс как таковой. Мы действуем на определение класса. Вот вам пример: несмотря на то что мы считаем P = BPP в реальном мире, очень легко построить оракул O, такой, что P^O ≠ BPP^O. Ясно, что если бы мы реально воздействовали на классы, то одинаковое воздействие на равные классы дало бы столь же равные результаты. Но на самом деле мы делаем не это, и, возможно, способ записи отчасти нас запутывает. Грубая аналогия: правда, что Обама — президент США, и правда также, что если бы Ромни выиграл выборы, то он был бы президентом. Но мы не можем просто не глядя подставить первое из этих уравнений во второе, ведь тогда нам придется заключить, что если бы Ромни выиграл выборы, то он был бы Обамой.

Таким образом, смысл релятивизации в том, что любой метод решения задачи «P или NP» или большинства других главных задач теории сложности просто обязан оказаться чувствительным к присутствию этих оракулов. Звучит не особенно впечатляюще, пока не сообразишь, что почти все знакомые нам методики доказательства не чувствительны к присутствию оракулов. Очень трудно отыскать методику, которая ощущала бы их присутствие, и поэтому — лично для меня — так интересны интерактивные доказательства. Они — ясный и недвусмысленный пример нерелятивизирующего способа, который я могу вам показать. Иными словами, мы можем доказать, что истинно нечто, что не было бы истинно, если бы вы просто снабдили все оракулом. Это можно рассматривать как первый шаг в неизвестность или как свет в конце тоннеля. По результатам интерактивного доказательства мы можем хотя бы очень приближенно судить о том, на что будут похожи доказательства разделения — когда-нибудь, если нам удастся их придумать. Методы интерактивного доказательства кажутся слишком слабыми, чтобы доказывать с их помощью что-нибудь вроде P ≠ NP, иначе вы бы непременно об этом услышали. Однако мы уже можем использовать эти методики для получения кое-каких нерелятивизирующих результатов разделения. Я покажу вам несколько примеров.

Как насчет P и BPP? Все сходятся во мнении, что P и BPP на самом деле равны. От Импальяццо и Вигдерсона[130] мы знаем, что если бы удалось доказать существование задачи, решаемой за время 2ⁿ, для чего требуются схемы размером 2^cn при некотором c > 0, то можно было бы построить очень хороший псевдослучайный генератор — такой, что его нельзя было бы отличить от случайного при помощи какой бы то ни было схемы фиксированного полиномиального размера. А если у вас есть такой генератор, его можно использовать для дерандомизации любого вероятностного алгоритма, полиномиального по времени. Можно скормить этому алгоритму данные, идущие с выхода псевдослучайного генератора, и алгоритм не сможет отличить его от по-настоящему случайной строки. Из этого следует, что вероятностный алгоритм может быть смоделирован с детерминистских позиций. Таким образом мы, кажется, в самом деле видим разницу между классической и квантовой случайностью. Представляется, что классическую случайность и правда можно эффективно смоделировать при помощи детерминистического алгоритма, тогда как квантовую «случайность» — нельзя. В данном случае интуиция подсказывает, что с классическим рандомизированным алгоритмом всегда можно просто «исключить случайность», то есть рассматривать алгоритм как детерминистический, а случайные биты как часть входного сигнала. С другой стороны, если нам хочется сымитировать квантовый алгоритм, то что может означать выражение «исключить квантовость»?

Итак, давайте посмотрим этот конкретный пример нерелятивизирующей методики. У нас есть булева формула (примерно такая, какие используются в SAT) от n переменных, удовлетворить которую невозможно. Нам хотелось бы получить доказательство ее неудовлетворимости. То есть мы бы хотели убедиться в том, что не существует никакого набора из n переменных, при которых наша формула даст результат «истина». Прежде мы это видели как пример co-NP-полной задачи. Проблема в том, что у нас недостаточно времени, чтобы перебрать все возможные варианты и убедиться, что все они не работают. В 1980-е годы был задан следующий вопрос: «Что, если у нас есть сверхразумный инопланетянин, который прилетает на Землю и может взаимодействовать с нами?» Мы не доверяем этому инопланетянину и его технологиям, но мы бы хотели, чтобы он доказал нам неудовлетворимость формулы таким способом, чтобы нам не нужно было проявлять доверие. Возможно ли это?

В теории вычислительной сложности, когда мы представления не имеем, как ответить на вопрос, мы часто довольствуемся тем, что находим «оракул», который делает ответ однозначным: да или нет. Пусть, к примеру, мы хотим удостовериться в том, что если нам дана булева схема, вычисляющая некоторую функцию f, то не существует полиномиального по времени алгоритма, который принимает в качестве входа описание схемы и надежно находит в f некую конкретную закономерность или регулярность. (Обратите внимание: значительная часть современной криптографии базируется на общепринятых представлениях такого рода!) Проблема в том, что обычно нет никакой надежды доказать подобную гипотезу, не доказав в качестве первого шага P ≠ NP! С другой стороны, очень часто мы можем доказать более слабое утверждение: что никакой полиномиальный по времени алгоритм не может обнаружить закономерность или регулярность, о которой идет речь, если он имеет доступ к f только как к черному ящику. То есть мы можем доказать, что если алгоритм может узнать об f, только выбирая x, а затем узнавая у волшебной подпрограммы значение f(x), то ему потребуется обратиться к этой подпрограмме экспоненциальное число раз.

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

Именно это проделали в конце 1980-х гг. Фортноу и Сипсер[131]. Хорошо, сказали они, предположим, у вас имеется экспоненциально длинная строка и какой-то пришелец хочет убедить вас в том, что эта экспоненциально длинная строка состоит из одних нулей. То есть в ней вообще нет ни одной единицы. Сможет ли доказатель это сделать? Представим, что из этого могло бы получиться.

Доказатель может сказать:

• В этой строке одни нули.

• Нет, я тебе не верю. Убеди меня.

• Ну вот, смотри, в этой позиции нуль. В этой тоже нуль. Так что в этой…

Ну хорошо, осталось проверить всего лишь 210 000 бит, и тут пришелец говорит:

• Поверь мне, там все нули.

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

Как всегда, мы можем определить новый класс сложности IP, отнеся к нему множество задач, где вас можно убедить в ответе «да» посредством взаимодействия с доказателем. Прежде мы говорили о таких классах, как MA и AM, где вы имеете постоянное число актов взаимодействия. В классе MA доказатель высылает вам сообщение, а вы проводите вероятностный расчет, чтобы его проверить. В классе AM вы посылаете доказателю сообщение, затем доказатель высылает вам ответное сообщение, а вы проводите вероятностный расчет. Выясняется, что с любым постоянным числом актов взаимодействия вы получаете один и тот же класс AM, так что не будем мелочиться и разрешим полиномиальное число взаимодействий. В результате получим класс IP. Что сделали Фортноу и Сипсер? Они привели способ построения оракула, относительно которого co-NP ⊄ IP. Они показали, что относительно этого оракула невозможно подтвердить невыполнимость формулы посредством полиномиального числа актов взаимодействия с доказателем. В соответствии со стандартной парадигмой данной области информатики мы, разумеется, не можем доказать безусловно, что co-NP ⊄ IP, но это все же дает нам кое-какие свидетельства; это указывает нам, истинность чего нам следует ожидать.

А теперь настоящая бомба (открыли ее Лунд, Фортноу, Карлофф и Нисан, отсюда название — «теорема LFKN»)[132]. Как показать в «реальном», нерелятивизированном мире невыполнимость формулы? Скорее всего, нам придется каким-то образом использовать структуру этой формулы. Придется воспользоваться тем, что это булева формула, заданная нам явно, а не абстрактная булева функция. Что мы сделаем? Будем считать, что это задача 3-SAT. Поскольку задача 3-SAT относится к NP-полным, это предположение не приведет к потере общности. У нас имеется некоторое количество условий (n штук), в каждом из которых задействовано по три переменных, и мы хотим удостовериться, что не существует способа удовлетворить всем условиям.

Что мы делаем? Отображаем нашу формулу на многочлен над конечным полем. Этот фокус называется арифметизацией. По существу, мы собираемся преобразовать данную логическую задачу в алгебраическую, что расширит наши возможности по работе с ней. Вот как это работает: мы записываем нашу реализацию 3-SAT в виде произведения многочленов третьей степени. Каждое условие — то есть каждое «или» трех литералов — просто превращается в 1 минус произведение 1 минус каждый из литералов: к примеру, (x или y или z) превращается в

1 — (1 — x ) (1 — y ) (1 — z ).

Обратите внимание: в случае, когда x, y и z могут принимать только значения 0 и 1, соответствующие значениям ложь и истина, этот многочлен в точности эквивалентен логическому выражению, с которого мы начали. Но теперь мы можем заново интерпретировать этот многочлен и сказать, что он определен над некоторым гораздо более обширным полем. Выберем некоторое достаточно большое простое число N, и мы скажем, что наш многочлен определен над GFN (полем из N элементов). Я обозначу этот многочлен P(x₁, …, x_n).

Если формула невыполнима, то какую бы подстановку x₁, …, x_n мы ни выбрали для переменных, в формуле непременно встретится какое-то условие, которое не будет выполнено. Следовательно, один из многочленов третьей степени, которые мы перемножаем, примет значение 0, а значит, и произведение будет равно нулю. Таким образом, отсутствие удовлетворительных назначений эквивалентно получению нуля при суммировании P(x₁, …, x_n) по всем 2ⁿ возможным булевым подстановкам x₁, …, x_n.

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

Итак, что мы теперь можем сделать? Мы просим доказателя просуммировать для нас по всем 2^n–1 возможным подстановкам переменных x₂, …, x_n, не фиксируя x₁. Таким образом, доказатель посылает нам одномерный многочлен Q₁ первой переменной. Поскольку многочлен, с которого мы начали, имел степень poly (n), доказатель может сделать это, прислав нам полиномиальное число коэффициентов. Он может прислать нам этот одномерный полином. Теперь мы должны убедиться в том, что Q₁(0) + Q₁(1) = 0 (все по модулю N). Как это сделать? Доказатель дал нам предполагаемое значение всего многочлена. Так что мы просто выбираем случайным образом r₁ из нашего поля. Далее нам бы хотелось убедиться в том, что Q₁(r₁) действительно равняется тому, чему должно равняться. Забудьте про 0 и 1, мы просто идем куда-то в другое место нашего поля. Далее, мы посылаем r₁ доказателю. В ответ доказатель посылает нам новый многочлен Q₂, в котором первая переменная фиксирована и равна r₁, вторая (x₂) не фиксирована, а x₃, …, x_n просуммированы по всем возможным булевым значениям (как раньше). Мы по-прежнему не знаем точно, что доказатель нам не лжет и не высылает бессмысленных многочленов. Что же мы можем сделать?

Проверяем, что Q₂(0) + Q₂(1) = Q₁(r₁), затем выбираем случайным образом другой элемент r₂ и вновь пересылаем его доказателю. В ответ он присылает нам многочлен Q₃(X). Это будет сумма P(x₁, …, x_n) по всем возможным булевым подстановкам x₄, …, x_n; x₁ при этом приравнивается к r₁, x₂ — к r₂, а x₃ не фиксируется. Опять же мы проверяем и убеждаемся, что Q₃(0) + Q₃(1) = Q₂(r₂). Далее продолжаем по накатанной: выбираем случайное r₃ и высылаем его доказателю. Так продолжается n итераций, на n-м шаге мы доходим до последней переменной. Что мы делаем тогда? В этот момент мы можем сами просто оценить P(r₁, …, rn), не прибегая к помощи доказателя, и непосредственно проверить его на равенство Q_n(r_n).

По пути мы проводим кучу проверок. Вот мое первое утверждение: если удовлетворяющего размещения не существует и если доказатель нам не лжет, то каждый из n тестов уверенно принимает. Второе утверждение: если бы удовлетворяющее размещение существовало, то с высокой вероятностью по крайней мере один из тестов не сошелся бы. Почему так? Мне кажется, что доказатель чем-то похож на девушку из сказки «Румпельштильцхен». Начав лгать, он будет все сильнее и сильнее запутываться в своей лжи, и в конце концов его ложь станет настолько явной, что мы сможем уличить его. Так все и происходит. Почему? Предположим, что на первой итерации доказатель должен выдать нам многочлен Q₁, но вместо этого выдает Q₁′. Но вот в чем дело: все это многочлены не слишком высоких степеней. Итоговый многочлен P имеет степень не более чем в три раза выше числа условий. Мы можем без труда сделать так, чтобы поле было больше размером. Так что пусть степень многочлена d будет много меньше, чем размер поля N.

Быстрый вопрос: предположим, у нас есть два многочлена P₁ и P₂ степени d. В скольких точках они могут быть равны между собой (предполагая, что они все же не идентичны)? Рассмотрим разность P₁ — P₂. Поскольку это тоже многочлен степени не выше d, согласно основной теореме алгебры он может иметь не более d различных корней (считая опять же, что многочлен не равен тождественно нулю). Таким образом, два многочлена, не равных между собой, могут совпадать не более чем в d точках, где d — степень многочленов. Это значит, что если это многочлены над полем размера N и мы выбираем в этом поле случайный элемент, то вероятность совпадения двух многочленов в этой точке будет ограничена сверху значением d/N.

Возвращаясь к протоколу, мы предполагали, что d много меньше N, так что вероятность совпадения Q₁ и Q₁′ на некотором случайном элементе поля много меньше единицы. Так что, когда мы случайно выбираем r₁, вероятность того, что Q₁(r₁) = Q₁′(r₁), не может быть больше d/N. Только если нам очень не повезет, можем мы выбрать r1, при котором значения окажутся одинаковыми; так что мы смело можем продолжать и считать, что Q₁(r₁) ≠ Q₁′(r₁). Далее вы можете представить себе, как доказатель мучается. Он пытается убедить нас во лжи, но, возможно, у него еще все получится. Но затем мы идем дальше и случайно выбираем r₂. Опять же вероятность того, что ему удастся впарить нам следующую ложь, будет не выше d/N. Эта верхняя оценка одинакова на всех итерациях, так что вероятность впарить нам любое из ложных утверждений не превышает nd/N. И нам просто нужно выбрать достаточно большое N, чтобы эта величина была много меньше единицы.

Почему нам просто не прогнать этот протокол над множеством положительных целых чисел? Потому что у нас нет способа генерации случайного положительного целого числа, а это нам потребуется. Так что мы просто выбираем очень большое конечное поле.

Итак, описанный протокол свидетельствует, что co-NP ⊆ IP. На самом деле он дает нам более сильное утверждение.

Стандартные рассуждения показывают нам, что самое большее, чем мог бы стать IP в наших самых смелых мечтах, это PSPACE. Вы можете доказать, что все, что можно сделать с интерактивным протоколом, можно также имитировать в PSPACE. Но можем ли мы подрастить IP? Сделать его побольше? До сих пор мы пытались проверить, что все эти величины P(x₁, …, x_n) в сумме дают нуль, но то же самое доказательство годилось бы и в том случае, если бы мы пытались убедиться в том, что в сумме они дают какую-то другую константу (любую, какую нам захочется).

Иными словами, с помощью Мерлина Артур может реально сосчитать число булевых строк x₁, …, x_n, таких, что P(x₁, …, x_n) = 1, а не просто решить, равняется ли это число нулю. Более формально, Артур может решить любую задачу из класса сложности #P (читается «sharp-P»), определенного Валиантом в 1979 г.[133]

Ну хорошо, время для небольшого отступления. В отличие от других классов сложности, виденных нами до сих пор, #P состоит не из задач принятия решения (да-или-нет), но из функций. Говорят, что функция f, отображающая двоичные строки на неотрицательные целые числа, входит в #P, если существует полиномиальный по времени алгоритм V и многочлен p, такие, что f(x) равна числу p(n) — битных строк w, которые заставляют V (x, w) принять. Проще говоря, #P есть класс всех задач, которые можно сформулировать в терминах подсчета числа решений некоторой NP-задачи. Далее, если мы спросим, как #P вписывается в картину классов сложности, которые мы уже видели, то столкнемся лицом к лицу с вопросом о сложении яблок и апельсинов: как сравнить класс функций с классами языков? Но простое решение, нередко используемое на практике, состоит в том, чтобы рассматривать класс P#P, состоящий из всех языков, разрешимых P-машиной с доступом к #P-оракулу.

Упражнение для неленивого читателя. Покажите, что P#^P = P^PP, где PP — это класс «мажоритарного голосования», определенный в главе 7. (То есть в определенном смысле PP «заранее содержит в себе латентную мощь #P».)

Чрезвычайно важный результат, доказанный в 1990 г. и получивший название теоремы Тоды[134], гласит, что P^#P содержит полиномиальную иерархию PH целиком. Если вам интуитивно не очевидно, почему оракул подсчета так силен, — ну, это и не должно быть очевидно! Теорема Тоды стала большим сюрпризом для всех. Как ни печально, у меня нет времени на обсуждение доказательства этой теоремы[135], но у меня до конца книги будет еще несколько поводов на нее сослаться.

Во всяком случае, в терминах классов сложности то, что мы видели выше, означает, что P^#P ⊆ IP: в интерактивном протоколе Мерлин может убедить Артура в решении любой задачи из #P и, соответственно, также любой задачи из P^#P (поскольку Артур может просто использовать Мерлина вместо #P-оракула). По теореме Тоды это, в свою очередь, означает, что IP содержит PH.

После этого появилась «теорема LFKN», множество людей приняло участие в дискуссии посредством электронной почты, и через месяц Шамир установил, что IP = PSPACE, то есть что IP действительно имеет максимально возможный размер[136]. Я не стану разбирать здесь результат Шамира, но это означает, что если бы на Землю прибыл сверхразумный пришелец, то он сумел бы доказать нам, имеют ли белые или черные в шахматах выигрышную стратегию, или же результат зависит от удачи. Разумеется, он мог бы сыграть с нами и выиграть, но в этом случае мы узнали бы только, что он лучше нас играет в шахматы. Но он мог бы доказать нам, кто из игроков имеет выигрышную стратегию, сведя шахматы к суммированию многочленов над большими конечными полями. (Техническое замечание: это работает только для шахмат с некоторым разумным ограничением на число ходов, таким как «правило пятидесяти ходов», используемое в турнирах.)

Для меня лично это уже достаточно контринтуитивно. Как я уже сказал, это позволяет нам получить хоть какое-то — очень слабое — представление о методиках, которые нам необходимо было бы использовать для доказательства нерелятивизирующих результатов, таких как P ≠ NP. Многие, кажется, думают, что ключевой момент здесь — каким-то образом преобразовать эти задачи из булевых в алгебраические. Вопрос в том, как это сделать. Но я могу показать вам, как эти методики уже позволяют нам получать кое-какие новые нижние оценки. Шутка сказать, даже нижние оценки для некоторых квантовых схем.

Первое утверждение: если мы вообразим, что существуют полиномиального размера схемы подсчета числа удовлетворяющих реализаций булевой формулы и что существует также способ доказать кому-то, чему равно число решений. Понимаете, почему это должно следовать из результата интерактивного доказательства? Ну, обратите внимание: чтобы убедить проверяющего относительно числа подходящих реализаций булевой формулы, доказатель сам по себе не должен иметь большую вычислительную мощность, чем требуется для подсчета числа реализаций. В конце концов, самому доказателю просто приходится все время вычислять эти экспоненциально большие суммы! Иными словами, доказатель для #P может быть реализован в #P. Если бы у вас был #P-оракул, то вы тоже могли бы сыграть роль доказателя. Исходя из этого факта, Лунд с соавторами указали, что если #P ⊂ P/poly, то есть если существует некоторая схема полиномиального по n размера для подсчета числа решений формулы размера n, то P^#P = MA. Потому что в MA Мерлин может дать Артуру полиномиальную по размеру схему для решения #P-задач, а затем Артуру достаточно будет просто проверить, что эта схема работает. Для этого Артур просто прогоняет описанный выше интерактивный протокол, в котором играет роли одновременно доказателя и проверяющего, и использует саму схему для моделирования доказателя. Это пример так называемых самопроверяющихся программ. Вам не нужно доверять предполагаемой схеме в подсчете числа решений формулы, поскольку вы можете поставить ее на место доказателя в интерактивном протоколе.

Теперь мы можем доказать, что класс PP, который состоит из задач, решаемых вероятностно за полиномиальное время с неограниченной ошибкой, не имеет схем линейного размера. Этим результатом мы первоначально обязаны Винодчандрану[137]. Почему так? Ну, здесь возможны два случая. Если PP не имеет схем даже полиномиального размера, то все понятно. С другой стороны, если PP все же имеет схемы полиномиального размера, то такие же схемы имеет и P^#P, по той простой причине (которую вам, возможно, доставит удовольствие доказать), что P^#P = P^PP. Далее, P^#P = MA по теореме LFKN, так что P^#P = MA = PP, поскольку PP зажат между MA и P^#P. Но можно доказать (и мы вскоре это сделаем), что P^#P не имеет схем линейного размера, при помощи прямой диагонализации. Таким образом, PP тоже не имеет схем линейного размера.

На самом деле вывод даже сильнее: для любого фиксированного k можно найти язык L класса P^#P или даже PP, такой, что L невозможно решить схемой размера O (n^k). Это совсем не то же самое, что сказать, что в PP имеется единственный язык, не имеющий схем полиномиального размера. Истинность второго утверждения показать невообразимо труднее! Если вы дадите мне свою (полиномиальную) оценку, то я найду PP-задачу, которая окажется не под силу схемам, ограниченным вашей оценкой, но эта задача тем не менее может оказаться решаемой схемами с другой полиномиальной оценкой, побольше. Чтобы выйти за пределы этой новой полиномиальной оценки, мне придется построить новую задачу, и так далее до бесконечности.

А теперь вернемся назад и дополним недостающий шаг в наших рассуждениях. Мы хотим показать для некоторого фиксированного k, что P^#P не решаем схемами размера n^k. Сколько существует возможных схем размера n^k? Где-то около . Тогда мы можем, посмотрев на поведение всех схем размера n^k, определить булеву функцию f. Упорядочим возможные входные строки размера n как x₁, …, x_2n. Если по крайней мере половина этих схем принимает x₁, приравняем f(x₁) = 0, а если по крайней мере половина схем отвергает x₁, приравняем f(x₁) = 1. Это устраняет по крайней мере половину схем размера n_k (то есть вызывает ошибку при вычислении f по крайней мере при одной входной строке). Далее, из тех схем, что выдают «верный ответ» для x₁, проверим, принимает ли большинство из них x₂ или отвергает. Если большинство принимает, приравниваем f(x₂) = 0. Если большинство отвергает, приравниваем f(x₂) = 1. Это опять же устраняет по крайней мере половину оставшихся схем. Продолжаем этот дарвиновский отбор дальше, и каждый раз, определяя новое значение функции, мы устраняем по крайней мере половину оставшихся схем размера n^k. После шагов окажется, что мы устранили все схемы размера n^k. Более того, процесс построения f включает полиномиальное число счетных задач, каждую из которых мы можем решить в P^#P. Так что конечный результат — задача из P^#P, не имеющая, однако, по построению схем размера n^k (для любого фиксированного k по нашему выбору). Это пример релятивизирующих рассуждений, поскольку мы не обращали внимания на то, имеют эти схемы какие бы то ни было оракулы или нет. Чтобы применить эти рассуждения не к P^#P, а к меньшему классу PP, нам пришлось использовать нерелятивизирующий компонент, а именно результат интерактивного доказательства по LFKN.

Но действительно ли это дает нам нижнюю оценку для нерелятивизирующей схемы? То есть существует ли оракул, относительно которого PP имеет схемы линейного размера? Много лет назад мне удалось построить такой оракул[138]. Это показывает, что результат Винодчандрана был нерелятивизирующим, — в самом деле, это один из немногих в теории сложности примеров неоспоримо нерелятивизирующего разделения. Иными словами, барьер релятивизации — один из главных препятствий в доказательстве P ≠ NP — может быть преодолен в некоторых очень ограниченных случаях.

Новые достижения

Во всяком случае, именно так обстояли дела, когда я в первый раз писал эту главу в 2006 г. С тех пор появились кое-какие очень интересные новости. Во-первых, в 2007 г. Рахул Сантханам[139] улучшил результат Винодчандрана и показал, что PromiseMA — класс всех задач с априорными ограничениями на входные данные с протоколами доказательства от Мерлина — Артура — не имеет схем размера nk для любого фиксированного k.

Вскоре после этого мы с Ави Вигдерсоном[140], вдохновленные результатом Сантханама, открыли новое препятствие к дальнейшему развитию теории сложности, которое мы назвали алгебраизацией. По существу, алгебраизация расширяет уже имевшийся барьер релятивизации по Бейкеру, Гиллу и Соловею в том, что когда мы изучаем вопрос о классах сложности относительно некоторого оракула A, мы теперь обеспечиваем одному из классов сложности доступ к «полиномиальному расширению невысокой степени» от A вместо самого A. Этот более мощный тип доступа к оракулу дает нам некоторый дополнительный рычаг воздействия; в частности, он позволяет нам сымитировать все стандартные нерелятивизирующие результаты, основанные на арифметизации. К примеру, хотя (как мы уже обсуждали) неверно, что IPA = PSPACEA для любого оракула A, тем не менее верно PSPACEA ⊆ IP~A, где ~A означает многочлен невысокой степени над большим конечным полем, который оказывается равным A, если получает на вход только булевы строки. Таким образом, мы говорим, что теорема IP = PSPACE «алгебраизирует», хотя и не релятивизирует. С другой стороны, мы с Ави показали также, что для большинства знаменитых открытых задач, включая не только «P или NP», но и «P или BPP», «NEXP или P/poly» и др., любое решение потребует «неалгебраизирующих методик», которые не проходят даже для этих новых алгебраических оракулов в том же смысле, в каком теорема IP = PSPACE не выполняется по отношению к обычным оракулам. Так что сухой остаток в том, что возможности методик, использованных для прорывных открытий с интерактивными доказательствами, тоже ограничены: конечно, они позволяют обойти барьер релятивизации, но лишь для того, чтобы воткнуться на полном ходу в барьер «обобщенной» релятивизации, ожидающий несколькими шагами дальше.

Существуют ли методики поиска нижней грани, позволяющие обойти как барьер релятивизации, так и барьер алгебраизации? Да; мало того, они известны уже не один десяток лет.

В начале 1980-х гг. Фурст, Сакс и Сипсер[141], а также (независимо) Айтаи[142] открыли революционную методику поиска нижних граней для размеров схем постоянной глубины (constant-depth circuits), к примеру схем AC⁰, состоящих из вентилей и, или и не, организованных в O (1) слои (где каждый вентиль и и или может иметь произвольное число входов). Фурст с соавторами и Айтаи показали, что для определенных функций, таких как четность n бит, любая схема AC⁰ должна иметь экспоненциальное число вентилей. Поскольку все участники активно использовали методы комбинаторики — в их основе лежало наблюдение за поведением реальных отдельных вентилей, — им удалось обойти барьер релятивизации. С тех пор аналогичными методами были доказаны и другие нижние оценки; особенно интересны работы Разборова[143] и Смоленского[144] для схем AC⁰, дополненных способностью к выполнению арифметических операций по модулю p (где p — некоторое фиксированное простое число).

К сожалению, в 1993 г. Разборов и Рудич указали[145], что почти все нижние оценки «комбинаторного типа» натыкаются на барьер, который они назвали «естественными доказательствами», — в некоторых отношениях он является дополнительным к барьеру релятивизации. Суть дела в двух словах: при применении комбинаторных методов поиска нижних оценок показывается, что определенные функции (к примеру, PARITY) являются трудными для небольших схем, потому что эти функции «похожи на случайные функции» в некотором эффективно вычислимом отношении, тогда как всякая функция, вычисляемая небольшой схемой должна выглядеть неслучайной в этом отношении. Однако любой аргумент такого сорта можно перевернуть с ног на голову и использовать для отличения «по-настоящему» случайных функций от псевдослучайных, решая таким образом, по иронии судьбы, некоторые из тех самых задач, трудность которых мы хотели доказать! Рассуждения Фурста и Ажтаи сработали именно потому, что схемы AC⁰ слишком слабы для вычисления псевдослучайных функций, мало того, невозможность псевдослучайности в AC⁰ может быть выведена как следствие доказательств нижней оценки. Но мы не можем ожидать, что какие-то аналогичные рассуждения сработают при доказательстве нижних оценок против более мощных классов схем, таких как P/poly, считая, как считает огромное большинство из нас, что эти классы и правда имеют псевдослучайные функции. (Говоря языком плаката, именно факт вычислительной трудности делает доказательство вычислительной трудности таким трудным!) Более того, Наор и Рейнгольд показали[146], что при правдоподобных криптографических допущениях даже класс TC⁰, состоящий из схем постоянной глубины с мажоритарными вентилями, способен вычислять псевдослучайные функции. Так что барьер естественных доказательств по Разборову — Рудичу, похоже, действительно выходит на сцену всего лишь «чуть» выше AC⁰.

Если вы хотите избежать барьера естественных доказательств, вам, судя по всему, потребуются методики, «пристрелянные» к некоторому особому свойству функции f, трудность которой вы пытаетесь доказать, — к свойству, которое не является общим для f и некоторой случайной функции. Очевидный пример методики, и правда сосредоточенной на таком особом свойстве, — «диагонализация», методика, какой мы пользовались ранее для доказательства того, что P#P не имеет схем линейного размера. (Вспомните, что наше доказательство пользовалось способностью #P-машины моделировать всевозможные схемы линейного размера и избегать моделирования со стороны любой из них.) Увы, но хотя такого рода методики позволяют обойти барьер естественного доказательства, именно они как раз и не позволяют обойти барьер релятивизации! Я имею в виду: да, они позволяют избежать релятивизации, если сдобрить их методиками интерактивных доказательств, но даже в этом случае они по-прежнему подпадают под барьер алгебраизации.

Итак, зададим очевидный следующий вопрос: существует ли нижняя оценка сложности схемы, позволяющая обойти все три барьера одновременно — и релятивизацию, и алгебраизацию, и естественные доказательства? По-моему, первый убедительный пример такой нижней оценки появился совсем недавно, в 2010 г., вместе с прорывным результатом Райана Уильямса[147], который гласит, что NEXP ⊄ ACC⁰. Здесь NEXP — недетерминистическое экспоненциальное время, тогда как ACC⁰ — легкое расширение AC⁰ с целью разрешить модулярную арифметику по любой базе (не забывайте, что мы уже знали бы нижнюю оценку, если бы AC⁰ был расширен до арифметики по модулю какого-то конкретного простого числа). Вы могли бы заметить, что этот результат кажется довольно жалким в сравнении с теми утверждениями, которые мы считаем истинными! Тем не менее это настоящая веха на нашем пути, потому что здесь удалось обойти все три известных барьера (строго говоря, мы не знаем, применим ли барьер естественного доказательства к ACC⁰, но если применим, то доказательство Уильямса его обходит!). Чтобы этого добиться, Уильямсу пришлось использовать «кухонную раковину» — диагонализацию, информацию от интерактивных доказательств и различные новые и старые результаты, посвященные нетривиальным структурам в функциях ACC⁰.

Существует ли четвертый барьер, который не в состоянии обойти даже новые результаты Уильямса? Я не знаю, спросите чего попроще! Общее правило гласит, что прежде чем думать о барьерах, стоящих перед какой-то заданной методикой, я бы сказал, что нам нужно по крайней мере два успешных примера приложения этой методики, примерно по той же причине, по какой нам нужно по крайней мере две точки, чтобы провести прямую.

Во всяком случае, одну вещь существующие нижние оценки сделали очевидной: а именно глубину идей, необходимых для доказательства даже нелепо простых по сравнению с P ≠ NP фактов. Именно поэтому у меня не вздрагивает сердце всякий раз, когда в моей почте появляется очередное заявленное доказательство P ≠ NP фактов (а они действительно там появляются не реже раза в месяц)! Дело не только в том, что я уже видел множество неудачных попыток; дело в том, что я всякий раз спрашиваю себя, как это обобщает, или включает в себя, или расширяет те нетривиальные решения крохотных подзадач глобальной проблемы «P или NP», которые нам уже известны.

Многие из нас (втайне?) боятся, что для дальнейшего прогресса в вопросе о нижних оценках сложности схем будет необходимо на порядки повысить математическую сложность в этой области информатики. Во всяком случае, это главное утверждение программы Кетана Мулмулея «Геометрическая теория сложности»[148], в которой с нижними оценками схем пытаются разобраться при помощи алгебраической геометрии, теории представлений и, кажется, всех иных средств, о которых только написаны учебники. Геометрическая теория сложности — сама по себе отдельная большая тема, и даже попытка объяснить ее увела бы меня слишком далеко в сторону. Просто скажу, что мне лично нравится называть геометрическую теорию сложности «теорией струн теоретической информатики»: с одной стороны, она сумела установить такие поразительные математические связи, что достаточно только взглянуть на них — и чувствуешь, что эта программа просто обязана быть на верном пути. С другой стороны, если судить об этой программе по тому, сколько ответов она сумела дать на вопросы, которыми изначально планировала заниматься, — вопросы, внешние по отношению к самой программе, — то пока первоначальные надежды не оправдываются.

Квантовые интерактивные доказательства

Пока нам приходится ждать продвижения в вопросе нижних оценок классических схем, позвольте мне вернуться назад и рассказать вам кое-что о квантовых системах интерактивных доказательств. Первое, мне кажется, что нужно сказать по этому поводу, — что даже результаты по нижним оценкам классических систем интерактивных доказательств — те, что мы уже видели, — можно использовать для получения нижних оценок квантовой схемы. Так, к примеру, слегка изменив наше доказательство того факта, что PP не имеет схем размера n^k, можно доказать, что PP не имеет даже квантовых схем размера n^k. Хорошо, но это еще цветочки. Давайте попытаемся добавить квантовый аспект к чему-то еще и получить иной ответ, нежели в классике.

Мы можем определить класс сложности QIP (Quantum Interactive Proofs). Это то же, что IP, но здесь вы — квантовый полиномиальный по времени проверятель, и вместо того чтобы обмениваться с доказателем классическими сообщениями, вы можете обмениваться сообщениями квантовыми. К примеру, вы могли бы послать доказателю половину ЭПР-пары, а вторую половину оставить себе — или поиграть с ним в какие-то другие подобные игры.

Конечно, этот класс по крайней мере столь же мощен, как IP, потому что при желании вы могли бы просто ограничиться классическими сообщениями. Поскольку IP = PSPACE, мы знаем также, что QIP должен быть по крайней мере столь же велик, как PSPACE. Воспользовавшись доводами полуопределенного программирования, Китаев и Ватрус[149] также доказали достаточно рано, что QIP ⊆ EXP. В 2006 г., когда я впервые писал эту главу, мы больше ничего, по существу, о классе QIP не знали. Но в 2009 г. Джейн, Цзи, Упадхиай и Ватрус совершили прорыв: они показали[150], что QIP можно смоделировать даже в PSPACE, и этому QIP = IP = PSPACE. Так что в конечном итоге оказалось, что квантовые интерактивные системы доказательства обладают ровно такой же мощностью, как и классические. Забавно, но в классическом случае самым удивительным было то, что эти системы могут имитировать PSPACE, тогда как в квантовом случае больше всего удивляло, что PSPACE может имитировать их!

Итак, существует ли какой-нибудь аспект, в котором квантовые интерактивные системы доказательства интересно отличаются от классических? Да, есть поразительный факт, который был доказан Китаевым и Ватрусом[151] и сыграл важнейшую роль в доказательстве теоремы QIP = PSPACE. Любой квантовый интерактивный протокол может быть сымитирован протоколом, реализуемым в три круга. В классическом случае нам пришлось отыгрывать ситуацию с Румпельштильцхеном: мы задавали доказателю один вопрос за другим, пока наконец не поймали его на лжи. Нам пришлось задать доказателю полиномиальное количество вопросов. Но в квантовом случае в этом больше нет необходимости. Доказатель посылает вам сообщение, вы посылаете ему ответ, затем доказатель посылает вам еще одно сообщении — и все. Это все, что вам может понадобиться.

Мы не будем здесь доказывать, почему это так, но я могу слегка намекнуть. По существу, доказатель подготавливает состояние, которое выглядит как Здесь r — последовательность всех случайных бит, которые вы использовали бы в классическом интерактивном протоколе. Скажем, мы берем классический протокол для решения задачи «co-NP или PSPACE» и хотим только смоделировать его при помощи трехступенчатого квантового протокола. Мы как бы сбиваем воедино все случайные биты, которые проверяющий использовал бы в протоколе, и берем суперпозицию по всем возможным подстановкам этих случайных бит. А что такое тогда q(r)? Это последовательность сообщений, которые доказатель должен был бы послать вам в ответ, если бы вы скормили ему случайные биты r. Далее, доказатель просто возьмет регистр q и второй регистр r и перешлет вам. Конечно, проверяющий может убедиться, что q(r) — правильная последовательность сообщений для заданного r. Но в чем же проблема? Почему этот протокол не годится?

Суперпозиция может браться по подмножеству возможных случайных битов! Откуда нам знать, что доказатель попросту не подобрал значение r, взяв его из тех, о которых он может успешно соврать? Выбирать задачи должен проверяющий. Нельзя допускать, чтобы за вас это делал доказатель. Но сейчас мы в квантовом мире, так что дела, возможно, обстоят лучше. Если представить себе, что в классическом мире существует способ убедиться в том, что тот или иной бит случаен, это, может быть, сработало бы. В квантовом мире такой способ действительно существует. К примеру, если дано состояние вроде

вы можете просто повернуть его и убедиться в том, что при измерении в стандартном базисе получите 0 и 1 с примерно равной вероятностью. Точнее, если результат измерения в стандартном базисе окажется случайным, то вы примете с вероятностью единица; если результат окажется далек от случайного, то вы отвергнете с заметной вероятностью.

И все же проблема в том, что наше |r〉 запутано с кубитами |q(r) 〉. Поэтому мы не можем просто применить операции Адамара к |r〉: если бы мы это сделали, мы бы получили в ответ просто мусор. Оказывается, однако, что проверяющий может выбрать случайный проход i моделируемого протокола — пусть всего имеется n таких проходов — и затем попросить доказателя развычислить все, что следует за проходом i. Как только доказатель это сделает, он тем самым ликвидирует запутанность, и тогда проверяющий сможет убедиться, проведя измерение в базисе Адамара, что биты прохода i действительно случайны. Если же доказатель смошенничал на каком-то проходе и выслал неслучайные биты, это позволит проверяющему обнаружить это с вероятностью, обратно пропорциональной числу проходов. Наконец, вы можете повторить весь протокол параллельно полиномиальное число раз, чтобы повысить уверенность в результате. (Я пропускаю многие подробности — моя цель в данном случае лишь намекнуть, натолкнуть на мысль.)

Сравним квантовую ситуацию с положением в классическом мире. Там у вас есть только MA и AM: любой доказательный протокол общения между Артуром и Мерлином с большим постоянным числом проходов схлопывается до AM. Разрешив полиномиальное число проходов, мы поднимаемся до класса IP (равному PSPACE). В квантовом мире у вас есть QMA, QAM, а еще QMAM, который есть то же самое, что QIP = PSPACE. Есть и еще один класс, QIP [2], который отличается от QAM тем, что Артур может переслать Мерлину любую произвольную строку (или даже квантовое состояние) вместо случайной строки. В классическом случае AM и IP [2] — это одно и то же, но в квантовом случае мы этого не знаем.

На этом наш обзор интерактивных доказательств завершается, и я закончу загадкой для следующей главы. Бог бросает честную монетку. Если монетка падает решкой, он создает комнату с рыжим человеком. Если орлом — то две комнаты, одну с рыжим, другую с зеленоволосым. Предположим, вы знаете, что кроме этого на свете ничего нет. Вы просыпаетесь и видите в комнате зеркало. Ваша цель — определить, какой стороной упала монетка. Если вы видите на себе зеленые волосы, все понятно. Но вот вопрос: если вы видите себя рыжим, какова вероятность того, что монетка упала орлом?