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

присылает нам многочлен Q3(X). Это будет сумма P(x1, …, xn) по всем возможным булевым подстановкам x4, …, xn; x1 при этом приравнивается к r1, x2 — к r2, а x3 не фиксируется. Опять же мы проверяем и убеждаемся, что Q3(0) + Q3(1) = Q2(r2). Далее продолжаем по накатанной: выбираем случайное r3 и высылаем его доказателю. Так продолжается n итераций, на n-м шаге мы доходим до последней переменной. Что мы делаем тогда? В этот момент мы можем сами просто оценить P(r1, …, rn), не прибегая к помощи доказателя, и непосредственно проверить его на равенство Qn(rn).

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

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

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

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

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

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

Иными словами, с помощью Мерлина Артур может реально сосчитать число булевых строк x1, …, xn, таких, что P(x1, …, xn) = 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 = PPP, где PP — это класс «мажоритарного голосования», определенный в главе 7. (То есть в определенном смысле PP «заранее содержит в себе латентную мощь #P».)

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