В последних двух главах мы говорили о вычислительной сложности до начала 1970-х гг. Здесь мы добавим в уже закипающее варево новый ингредиент — нечто, что возникло в нашем контексте примерно в середине 1970-х гг. и что теперь пропитывает понятие вычислительной сложности в такой степени, что сложно представить без него любое действие в этой области. Этот новый ингредиент — концепция случайности.

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

Итак, что такое случайность? Вообще-то это глубокий философский вопрос, но я человек простой. Поэтому мы имеем некоторую вероятность p, представляющую собой действительное число в единичном интервале [0, 1]. Это и есть случайность.

Но разве не было в этой области крупного достижения в 1930-е гг., когда Колмогоров подвел под вероятность аксиоматический базис? Да, было! Но в этой главе нас интересует только распределение вероятностей по конечному числу событий, так что тонкие вопросы интегрируемости, измеримости и т. п. у нас не возникнут. На мой взгляд, теория вероятностей — это еще один пример области, в которой математики сразу же уходят в пространства бесконечных размерностей, чтобы решить для себя проблему безделья и найти побольше нетривиальных задач для решения! И это прекрасно — чем бы дитя ни тешилось. Я вовсе не критикую. Но нам в теоретической информатике вполне хватает возни с выбором из 2ⁿ вариантов. Выбор из 2^ℵ₀ нужен нам, как пятое колесо в телеге.

Ну хорошо, пусть нам дано некоторое «событие» A — скажем, что завтра пойдет дождь, и мы можем говорить о действительном числе Pr [A], лежащем в [0, 1], которое представляет собой вероятность того, что A произойдет. (Или, скорее, вероятность, с которой мы думаем, что A произойдет, — но я уже говорил вам, что я человек простой.) Кроме того, вероятности различных событий состоят в некоторых очевидных отношениях, но нам, возможно, полезно будет посмотреть их в явном виде, на случай, если вы никогда их не видели.

Во-первых, вероятность того, что A не произойдет, равна 1 минус вероятность того, что A произойдет:

Pr[не (A)] = 1 — Pr[A].

Согласны? Я так и думал.

Во-вторых, если у нас есть два события, A и B, то

Pr[A или B] = Pr[A] + Pr[B] — Pr[A и B].

В-третьих, непосредственное следствие из вышесказанного, известное как неравенство Буля, или аддитивное неравенство или граница объединения:

Pr[A или B] ≤ Pr[A] + Pr[B].

Или на обычном языке: если маловероятно, что вы утонете, и маловероятно, что станете жертвой удара молнии, то у вас хорошие шансы на то, что вы и не утонете, и не погибнете от удара молнии, независимо от того, повышает или понижает удар молнии ваши шансы утонуть. Один из немногих поводов для оптимизма в этой жизни.

Несмотря на тривиальность, граница объединения является, вероятно, самым полезным фактом во всей теоретической информатике. Я лично использую это свойство раз по 200 в каждой своей статье.

Что еще? Если задана случайная числовая переменная X, то математическое ожидание X, или E[X], определяется как Σ_k Pr[X = k]k. Тогда если даны две произвольные случайные переменные X и Y, то

E[ X + Y ] = E[ X ] + E[ Y ].

Это называется линейностью математического ожидания, и это, вероятно, второй по полезности факт во всей теоретической информатике после границы объединения. Опять же самое важное здесь — что любые зависимости между X и Y не имеют значения.

Может быть, выполнятся также и соотношение

E [ XY ] = E[ X ] E[ Y ]?

Разумеется, не выполняется! Впрочем, выполняется, если X и Y независимы, но не в общем случае.

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

Pr[X≥kE[X]] ≤ 1/k.

Почему? Ну, если бы X слишком часто имело значение, слишком во много раз превосходящее его математическое ожидание, то даже если бы все остальное время X было равно 0, этого все равно было бы недостаточно, чтобы скомпенсировать отклонение матожидания.

Неравенство Маркова сразу же ведет к третьему полезнейшему факту теоретической информатики, известному как граница Чернова. Граница Чернова, по сути, означает, что если вы бросили монетку 1000 раз и при этом 900 раз выпал орел, то очень велики шансы на то, что монетка неправильная. Именно на эту теорему неявно опираются менеджеры казино, когда решают, посылать ли своих горилл ломать ноги игроку после крупного выигрыша.

Теоретически пусть h — число выпадений орла при бросании правильной монетки n раз. Тогда один из способов определить границу Чернова — это

где c — постоянная, которую вы можете уточнить, если не помните. (Ну хорошо, хорошо: c = 2 годится.)

Как мы можем доказать границу Чернова? Ну, есть такой простой фокус: пусть x_i = 1, если i-я монетка падает орлом, и x_i = 0, если решкой. Рассмотрим математическое ожидание, не самой суммы x₁ + … + x_n, а ее экспоненты exp (x₁ + … + x_n). Поскольку броски монетки, по идее, не должны коррелировать между собой, мы имеем

Теперь мы можем просто воспользоваться неравенством Маркова, а затем взять логарифмы обеих сторон, чтобы получить границу Чернова. Я избавлю вас от скучных вычислений (или, скорее, себя избавлю).

Для чего нам нужна случайность?

Даже великие древние — Тьюринг, Шеннон и фон Нейман — понимали, что источник случайных чисел может оказаться полезен при написании программ. Так, к примеру, еще в 1940-е и 1950-е гг. физики придумали метод математического моделирования, названный методом Монте-Карло, для изучения какого-то странного вопроса, который им был в тот момент интересен и который был как-то связан с имплозией, или направленным внутрь взрывом, полых плутониевых шаров. Метод Монте-Карло означает просто сбор информации о типичном или среднем поведении возможно сложной динамической системы не путем явного вычисления средних значений различных интересующих вас величин, а просто путем моделирования системы много раз с различными случайными начальными состояниями и сбора статистических данных. Статистическая выборка — скажем, различных способов, которыми полый плутониевый шар может сделать Большой Бабах, — это совершенно законное использование случайности.

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

Посмотрим пример рандомизированного алгоритма (алгоритма с элементом случайности). Предположим, я описываю вам число следующим образом: начинаю с 1 и затем многократно добавляю, вычитаю или умножаю два числа, которые уже были упомянуты ранее (как в карточной игре «24»). Примерно так:

a = 1

b = a + a

c = b²

d = c²

e = d²

f = e — a

g = d — a

h = d + a

i = gh

j = f — i.

Вы можете самостоятельно убедиться (если возникнет такое желание), что j, «выход» приведенной выше программы, равняется нулю. А теперь рассмотрите следующую обобщенную задачу: если дана такая программа, будет у нее на выходе 0 или нет? Как можно это определить?

Ну, один из способов — просто выполнить программу и посмотреть, что получится у нее на выходе! В чем проблема?

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

Что еще можно сделать? Ну, предположим, у нас в программе n операций. Тогда можно попробовать следующий фокус: для начала взять случайное простое число p из n² знаков. Затем смоделировать работу программы, но все вычисления делать по модулю p. Здесь возникает сверхважный момент, который для начинающих часто становится ловушкой: единственное, где нашему алгоритму разрешается использовать случайность, — это в моменты его собственного выбора, в данном случае — в момент выбора случайного простого числа p. Нам не разрешается рассматривать никакие усреднения по возможным программам, поскольку программа является просто входом в алгоритм, а со входом у нас все плохо!

Что мы можем сказать о приведенном выше алгоритме? Ну, он, безусловно, будет эффективен, то есть он будет выполняться за время, полиномиальное по отношению к n. Кроме того, если результат окажется не равен нулю по модулю p, то можно однозначно заключить, что он и вообще не равен нулю. Однако это оставляет без ответа два вопроса:

1. Предполагая, что результат равен 0 по модулю p, насколько уверены вы можете быть в том, что это не просто удачное совпадение и что результат и в самом деле равен 0?

2. Как выбрать случайное простое число?

Что касается первого вопроса, пусть x — результат работы программы. Тогда |x| не может быть больше 2^2ⁿ, где n — число действий, поскольку самый быстрый доступный нам способ получения больших чисел заключается в последовательном возведении в квадрат. Из этого сразу же следует, что у x может быть не более 2ⁿ простых делителей.

С другой стороны, сколько существует простых чисел из n² знаков? Знаменитая теорема о числе простых чисел дает ответ на этот вопрос: примерно 2^2ⁿ/n². Поскольку 2^2ⁿ/n² намного больше, чем 2ⁿ, на большинство этих простых чисел x, понятно, не разделится. Так что если мы выбираем случайное простое число и x на него делится, мы можем быть весьма и весьма уверены (правда, все же не абсолютно), что x = 0.

С первым вопросом разобрались. Теперь ко второму: как выбрать случайное простое число из n² знаков? Наш старый приятель, теорема о числе простых чисел, говорит нам, что если выбрать просто случайное число из n² знаков, оно окажется простым примерно в одном случае из n². Так что вам нужно всего лишь выбирать раз за разом случайные числа; примерно через n² попыток вы, вероятно, наткнетесь на простое число! Но почему, вместо того чтобы перебирать случайные числа, нельзя просто взять какое-то фиксированное число, а затем прибавлять к нему по единице, пока не дойдешь до простого числа?

Да, конечно, это сработает при условии одного весьма сильного обобщения гипотезы Римана! Нужно лишь, чтобы эти самые n²-значные простые числа были более или менее равномерно распределены по числовой прямой, так чтобы вы не могли в результате чистого невезения угодить на экспоненциально длинный промежуток, где все числа будут составными. Даже обобщенная гипотеза Римана не может вам этого гарантировать; впрочем, существует еще так называемая гипотеза Крамера — вот она может.

Разумеется, мы всего лишь свели задачу выбора случайного простого числа к другой задаче, а именно: как определить, выбрав случайное число, что оно простое? В предыдущей главе я упоминал, что определить, простое число или составное, оказывается, намного проще, чем действительно разложить число на множители. До недавнего времени задача проверки на простоту служила еще одним примером задачи, где, казалось, необходимо использовать случайность, мало того, она была бабушкой всех таких задач.

Идея состояла в следующем. Малая теорема Ферма (не путать с Великой теоремой Ферма!) гласит, что если p — простое число, то x^p = x(mod p) для любого целого x. Так что если вы нашли x, для которого x^p ≠ x(mod p), то вы можете быть уверены, что p — число составное, хотя по-прежнему ничего не будете знать о его делителях. А потому если вам долго и упорно не удается найти такое x, для которого xp ≠ x(mod p), то можно с высокой степенью уверенности сказать, что p — простое.

Увы, эта простая идея не работает. Оказывается, существуют составные числа p, которые «притворяются» простыми в том смысле, что для них x^p = x(mod p) для любого x. Первые несколько таких «притворщиков» (названных числами Кармайкла) — это 561, 1105, 1729, 2465 и 2821. Конечно, если бы «притворщиков» было лишь конечное число и мы бы их все знали, все было бы прекрасно. Но Олфорд, Грэнвилл и Померанс[32] показали в 1994 г., что чисел-«притворщиков» существует бесконечно много.

К счастью, еще в 1976 г. Миллер и Рабин нашли способ разоблачить притворщиков, слегка изменив тот же тест. Иными словами, они нашли такую модификацию теста Ферма, которая всегда проходит при простом p, а вот в случае составного — с высокой вероятностью не проходит. Отсюда был получен рандомизированный алгоритм проверки на простоту за полиномиальное время.

Затем, лет десять назад, произошел прорыв, о котором вы, вероятно, слышали. Аграваль, Кайал и Саксена[33] нашли детерминированный алгоритм полиномиального времени, позволяющий определить, является ли число простым. Это прорывное открытие не имеет совершенно никакого практического применения, поскольку у нас давно есть более быстрые рандомизированные алгоритмы, для которых вероятность ошибки можно без труда низвести до величины меньшей, чем вероятность падения астероида на ваш компьютер в разгар вычислений. Но знать, что такой алгоритм существует, очень приятно.

Просуммируем сказанное. Мы хотели получить эффективный алгоритм, который проверял бы программу, целиком состоящую из операций сложения, вычитания и умножения, и определял бы, получится ли в результате вычислений 0. Я дал вам такой алгоритм, но он нуждается в случайности в двух местах: во-первых, при выборе некоторого случайного числа и, во-вторых, при проверке этого случайного числа на простоту. Оказалось, что второе применение случайности не принципиально, поскольку у нас теперь есть детерминированный полиномиальный по времени алгоритм проверки на простоту. Но как быть с первым использованием случайности? Может быть, в нем тоже нет нужды? Так вот, по состоянию на 2013 г. никто этого еще не знает! Но орудия главных теоретических калибров уже долбят эту проблему, и ситуация легко может измениться. Справьтесь о том, как развивается эта ситуация, в материалах вашей местной конференции по теоретической информатике.

Отлично, пора нам определить кое-какие классы сложности. (Да, если подумать, когда не пора это делать?)

Когда мы говорим о вероятностных вычислениях, скорее всего, речь идет об одном из следующих четырех классов сложности, которые Джон Гилл[34] определил в работе, опубликованной в 1977 г.

• PP (Probabilistic Polynomial-Time, вероятностный за полиномиальное время). Ну да, видимо, даже сам Гилл признавал, что это сокращение не самое удачное. Оно ведь произносится… нет, у нас серьезная книга, и я не допущу юмора на уровне седьмого класса. В сущности, PP — это класс всех проблем разрешимости, для которых существует рандомизированный алгоритм за полиномиальное время, который принимает с вероятностью большей 1/2, если ответ «да», либо меньшей 1/2, если ответ «нет». Иными словами, мы представляем себе специфическую машину Тьюринга M, получающую не только n-битную входную строку x, но и неограниченный источник случайных битов. Если x — это «да-строка», то по крайней мере половину случайных битовых данных M должна принимать; тогда как если x является «нет-строкой», то по крайней мере половину случайных битовых данных M должна отвергать. Более того, M должна останавливаться после некоторого числа шагов (число это обязано быть полиномиальным по n).

Вот стандартный пример PP-задачи: если дана булева формула Φ с n переменными, то дает ли по крайней мере половина из 2ⁿ возможных комбинаций входных переменных результат «истина»? (Кстати говоря, в точности как поиск ответа на вопрос, существует ли удовлетворительная входная комбинация, относится к числу NP-полных задач, так и здесь можно показать, что задача с голосованием является PP-полной, то есть любая другая PP-задача эффективно сводится к ней.)

Хорошо, почему же тогда PP не стыкуется с нашим интуитивным представлением о задачах, решаемых рандомизированными алгоритмами?

Верно: потому что мы хотим избежать ситуаций типа «флоридского пересчета»[35]! Там, где речь идет о PP, алгоритм волен принимать с вероятностью 1/2 + 2^—n, если ответ «да», и вероятностью 1/2 — 2^—n, если ответ «нет». Но как простому смертному различить эти два случая в реальности? Если n равняется, скажем, 5000, то нам придется накапливать статистику за период времени, превышающий возраст Вселенной!

Кроме того, PP — чрезвычайно большой класс, к примеру, он определенно включает в себя NP-полные задачи. Почему? Ну, если дана булева формула φ с n переменными, вы можете сделать так: с вероятностью 1/2 — 2^–2n принять не глядя, а в противном случае выбрать случайное размещение и принять его в том и только том случае, если оно удовлетворяет φ. Тогда полная вероятность принятия у вас получится больше 1/2, если по крайней мере одно выполнимое размещение для Φ существует, и меньше 1/2, если такого размещения не существует.

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

Приведенные выше соображения заставили Гилла определить более «разумный» вариант PP, вот такой.

• BPP (Bounded-Error Probabilistic Polynomial-Time, вероятностный за полиномиальное время с ограниченной ошибкой). Это класс проблем разрешимости, для которых существует рандомизированный алгоритм за полиномиальное время, который принимает с вероятностью большей 2/3, если ответ «да», или меньшей 1/3, если ответ «нет». Иными словами, при любых входных данных такой алгоритм может ошибаться с вероятностью не более 1/3.

В отношении 1/3 важно исключительно то, что это какая-то положительная константа, меньшая 1/2. Любая такая константа подошла бы не хуже. Почему? Ну, предположим, нам задан BPP-алгоритм, который ошибается с вероятностью 1/3. При желании мы можем без труда модифицировать этот алгоритм так, чтобы он ошибался с вероятностью не более, скажем, 2^–100. Как?

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

На самом деле мы не просто могли бы заменить 1/3 любой другой константой, меньшей 1/2; мы могли бы даже заменить ее на 1/2 — 1/p(n), где p — произвольный полином.

Так что же такое BPP? Если хотите, это класс всех задач, которые возможно решить при помощи компьютера во Вселенной, где правит классическая физика.

• RP (Randomized Polynomial-Time, рандомизированный, полиномиального времени). Как я уже говорил, вероятность ошибки алгоритма BPP можно без труда уменьшить до такой степени, что она будет меньше вероятности попадания астероида в ваш компьютер. И этого достаточно для большинства приложений: скажем, для отслеживания доз облучения в больнице, для шифрования многомиллиардных банковских операций или для управления пусками ядерных ракет. Но как насчет доказывания теорем? В некоторых приложениях рисковать просто нельзя.

Вот тут-то мы и приходим к RP — к классу задач, для которых существует рандомизированный алгоритм за полиномиальное время, который принимает с вероятностью более 1/2, если ответ «да», или с вероятностью нуль, если ответ «нет». Сформулируем иначе: если алгоритм принимает хотя бы раз, то вы можете быть абсолютно уверены, что ответ «да». Если алгоритм отвергает варианты один за другим, то вы можете очень уверенно предполагать (но не гарантировать), что ответ «нет».

У RP есть очевидное «дополнение», называемое co-RP. Это просто класс задач, для которых существует рандомизированный алгоритм за полиномиальное время, который принимает с вероятностью 1, если ответ «да», или с вероятностью менее 1/2, если ответ «нет».

• ZPP (Zero-Error Probabilistic Polynomial-Time, вероятностный, полиномиального времени, с нулевой ошибкой). Этот класс может быть определен как пересечение RP и co-RP — класс задач, относящихся к обоим этим классам одновременно. Можно также сказать, что ZPP — это касс задач, решаемых рандомизированным алгоритмом за полиномиальное время, который обязан выдавать верный ответ всякий раз, когда он его выдает, но в части случаев (до половины) может выдавать ответ «не знаю». Опять же можно дать и такую эквивалентную формулировку: ZPP — это класс задач, решаемых алгоритмом, который никогда не ошибается, но время выполнения которого ожидаемо полиномиальное.

Иногда можно увидеть, как BPP-алгоритмы называют алгоритмы Монте-Карло, а ZPP-алгоритмы — алгоритмы Лас-Вегаса. Мне случалось даже встречать RP-алгоритмы под названием «алгоритмы Атлантик-Сити»[36]. Такая терминология всегда казалась мне глупой. (Может, существуют еще и алгоритмы индейских резерваций?)

Изобразим графически известные отношения между базовыми классами сложности, которые встречались нам уже в этой книге. Отношения, о которых я не рассказывал в явном виде, оставлены в качестве упражнений для читателей (то есть для вас).

Вас, может быть, удивит, но мы до сих пор не знаем, входит ли BPP в NP. Но подумайте: даже если бы BPP-машина принимала с вероятностью, близкой к 1, как бы вы доказали это детерминированной программе-верификатору за полиномиальное время, вовсе не склонной вам верить? Конечно, вы могли бы показать верификатору некоторое количество случайных прогонов машины, но и после этого она бы продолжала подозревать вас в том, что вы специально подобрали образцы так, чтобы получить желаемый ответ.

К счастью, ситуация не настолько неприятна, как кажется: мы по крайней мере знаем, что BPP входит в NP^NP (то есть в NP с NP-оракулом) и, следовательно, во второй уровень полиномиальной иерархии PH. Сипсер, Гач и Лаутеман доказали это в 1983 г. Это доказательство я вообще-то собираюсь пропустить, технически оно достаточно сложное. Если вам интересно, посмотреть можно здесь[37].

Кстати говоря, если мы знаем, что BPP входит в NP^NP, то относительно BQP мы ничего такого не знаем. BQP — это класс задач, решаемых за полиномиальное время на квантовом компьютере. BQP в этой книге пока официально не представлен, — вам придется подождать еще пару глав! — но я хочу предвосхитить в какой-то степени его появление и рассказать, чем он, судя по всему, не является. Иными словами, что, как нам известно, верно в отношении BPP такого, о чем мы не можем сказать, верно ли оно в отношении BQP? Включение в PH — это лишь первый из трех примеров, с которыми мы познакомимся в этой главе.

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

Но даже в мире с неоднородностью, уверены специалисты по теории вычислительной сложности, должны существовать серьезные ограничения на то, что может быть эффективно вычислено. Желая поговорить об этих пределах, мы пользуемся терминологией, придуманной Карпом и Липтоном в 1982 г.[38] Карп и Липтон определили, класс сложности P/f(n), или P с советом размера f(n), как состоящий из всех задач, решаемых за детерминированное полиномиальное время на машине Тьюринга при помощи f(n) — битной «строки совета» a_n, зависящей только от длины входной строки n.

Вы можете думать о полиномиальной по времени машине Тьюринга как об аспиранте, а о строке совета a_n как о мудрости его научного руководителя. Как и большинство руководителей, он бесконечно мудр, благожелателен и надежен. Он ничего так не жаждет, как помогать своим аспирантам решать проблемы с их диссертациями, то есть определять, являются ли их входные строки x из {0, 1}ⁿ да-строками или нет-строками. Но, опять же как большинство научных руководителей, он слишком занят, чтобы выяснять, над какими конкретно задачами работают в данный момент его аспиранты. Поэтому он просто выдает им всем один и тот же совет a_n, позволяя каждому применить его к своим входным данным x.

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

Нам будет особенно интересен класс P/poly, который состоит из всех задач, решаемых за полиномиальное время с использованием совета полиномиального размера. Иными словами, P/poly есть объединение P/n^k по всем положительным целым k.

Далее, возможно ли, что P = P/poly? В качестве первого (тривиального) наблюдения я заявляю: ответ «нет» — P строго содержится в P/poly и, более того, в P/1. Иными словами, даже с единственным битом совета вы в состоянии сделать больше, чем вообще без совета. Почему?

Верно! Рассмотрим следующую задачу:

Если задана входная строка длиной n, определите, остановится ли n-я машина Тьюринга.

Мало того, что эта задача не входит в P, она даже не является вычислимой, ведь она представляет собой не что иное, как медленное, «унарное» шифрование проблемы остановки. С другой стороны, ее легко решить при помощи единственного бита совета, который зависит только от длины входной строки n. Ибо этот бит совета способен просто сказать вам, чему равен ответ!

Вот еще один способ понять мощь совета: если число задач в P — всего лишь счетная бесконечность (почему?), то число задач в P/1 — бесконечность уже несчетная (почему?).

С другой стороны, один тот факт, что с советом можно решить намного-намного больше задач, чем без него, не означает, что совет поможет вам решить любую конкретную задачу, которая вас, возможно, интересует. В самом деле, второе несложное наблюдение состоит в том, что совет не всемогущ: существуют задачи, не входящие в P/poly. Почему?

Ну, здесь можно привести простой аргумент с диагонализацией. Я покажу даже более сильный результат: существуют задачи, не входящие в P/n^{log n}. Пусть M₁, M₂, M₃, … — список полиномиальных по времени машин Тьюринга. Кроме того, зафиксируем длину входной строки n. Я утверждаю, что существует булева функция f: {0, 1}ⁿ → {0, 1}, которую первым n машинам (M₁,…, M_n) не удается вычислить даже при наличии любой n^{log n}-битной строки совета. Почему? Просто посчитаем: существует 2^2ⁿ булевых функций, но только n машин Тьюринга и строк совета. Поэтому выберите такую функцию f для каждого n; при этом каждую машину Mi, ждет неудача при всех длинах, за исключением конечного их числа. Вот и все, нам не потребовалось даже условие, что M_i работает полиномиальное время.

Почему для меня так важен совет? Во-первых, он появляется снова и снова, даже если нас, к примеру, интересуют лишь однородные вычисления. Даже если мы хотим узнать всего лишь, можно ли дерандомизировать BPP, оказывается, что и этот вопрос имеет отношение к совету. Так что совет очень тесно связан с остальными понятиями вычислительной сложности. По существу, можно считать, что алгоритм с советом ничем не отличается от бесконечной последовательности алгоритмов, точно как мы видели в случае теоремы ускорения Блума. Это всего лишь алгоритм, где по мере увеличения длины входной строки вам приходится использовать все новые идеи и добиваться все большего ускорения. Совет можно, в частности, рассматривать так.

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

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

Разумеется, все это время мы с вами танцевали вокруг настоящего вопроса: может ли совет помочь нам в решении задач, которые нас действительно интересуют, таких как NP-полные задачи? В частности, верно ли, что NP ⊂ P/poly? Интуитивно представляется, что вряд ли: булевых формул размера n экспоненциально много, так что если бы вы даже получили каким-то образом от Бога строку совета полиномиального размера, то как бы это помогло вам определить выполнимость больше чем крохотной части этих формул?

Но — и я уверен, что для вас это станет полнейшим шоком, — мы не можем доказать, что это невозможно. Правда, в данном случае у нашего невежества есть хорошее оправдание, поскольку если P = NP, то, очевидно, верно также и NP ⊂ P/poly. Но вот вопрос: если бы нам удалось доказать P ≠ NP, то доказали бы мы тем самым, что NP ⊄ P/poly? Иными словами, следует ли из NP ⊂ P/poly, что P = NP? Увы, мы не знаем ответа даже на этот вопрос.

Но, как и в случае с BPP и NP, ситуация не настолько неприятна, как кажется. Карпу и Липтону все же удалось доказать в 1982 г., что если NP ⊂ P/poly, то полиномиальная иерархия PH схлопывается до второго уровня (то есть до NP^NP). Иными словами, если вы верите, что полиномиальная иерархия бесконечна, вы должны также верить, что NP-полные задачи не решаются эффективно неоднородными алгоритмами.

Эта теорема Карпа — Липтона — самый известный пример очень обширного класса результатов теории вычислительной сложности, класса, который описывают формулировкой «если бы ослы умели свистеть, то свиньи умели бы летать». Иными словами, если бы одна вещь, в истинность которой никто не верит, была бы истинна, то истинна была бы и другая вещь, в истинность которой тоже никто не верит! Интеллектуальный онанизм, говорите? Чепуха! Интересно здесь то, что обе эти вещи, в истинность которых никто не верит, прежде казались совершенно не связанными одна с другой.

Замечание немного не в тему, но доказательство теоремы Карпа — Липтона будет поинтереснее целой бочки карпов. Поэтому рассмотрим его прямо сейчас. Предположим, что NP ⊂ P/poly; нужно доказать, что полиномиальная иерархия схлопнется до второго уровня, или, что эквивалентно, что co-NP^NP = NP^NP. Рассмотрим произвольную задачу в co-NP^NP, примерно такую:

Для всех n-битных строк x существует ли n-битная строка y, такая, что Φ (x, y) дает результат «истина»?

(Здесь Φ — некоторая произвольная полиномиального размера булева формула.)

Нам нужно найти вопрос из NPNP, то есть вопрос, в котором квантор существования идет впереди квантора общности, ответ на который совпадает с ответом на приведенный выше вопрос. Но что это может быть за вопрос? Уловка тут вот в чем: сначала мы используем квантор существования, чтобы угадать полиномиального размера строку совета an. Затем мы используем квантор общности, чтобы угадать строку x. Наконец, мы используем строку совета an, — вместе с предположением, что NP ⊂ P/poly, — чтобы самостоятельно угадать y. Таким образом:

Существует ли строка совета an, такая, что для всех n-битных строк x булева формула φ(x, M(x, a_n)) дает результат «истина»?

Здесь M — это полиномиальная по времени машина Тьюринга, которая при заданном входе x и совете a_n выдает в качестве результата n-битную строку y, такую, что φ(x, y) дает при вычислении «истину» всякий раз, когда такой y существует. По аналогии с одной из задач предыдущей главы мы можем без труда построить такую M при условии, что умеем решать NP-полные задачи в P/poly.

Ну хорошо, я уже рассказывал, что неоднородность тесно связана со случайностью — настолько, что трудно говорить об одной, не упоминая другой. Так что в конце этой главы я хочу рассказать вам о двух моментах, связывающих случайность и неоднородность: о простой связи, открытой Адлеманом в 1970-е гг., и второй, глубокой, которую открыли Импальяццо, Нисан и Вигдерсон в 1990-е гг.

Простая связь заключается в том, что BPP ⊂ P/poly, иными словами, неоднородность по крайней мере столь же мощна, как и случайность. Почему так, как вы считаете?

Ну давайте посмотрим, почему. Имея некоторое BPP-вычисление, первое, что мы делаем, — это усиливаем вычисление до экспоненциально малой ошибки. Иными словами, мы повторяем вычисление, скажем, n² раз, а затем выводим ответ, полученный в большинстве случаев, так что вероятность сделать ошибку падает с 1/3 до примерно 2^-n². (Если вы пытаетесь доказать что-то относительно BPP, усиление до экспоненциально малой ошибки почти всегда представляет собой удачный первый шаг!)

Далее. Сколько существует входных строк длины n? Верно: 2ⁿ. И для каждой входной строки лишь 2^-n² доля случайных строк приводит нас к ошибке. Согласно границе объединения (как мы помним, это самый полезный факт во всей теоретической информатике), из этого следует, что не более 2^n-n² доли случайных строк вообще могут привести нас к ошибке на входных строках длины n. Поскольку 2^n-n²< 1, это означает, что существует некая случайная строка, назовем ее r, которая никогда не вызывает ошибки на входных строках длины n. Так что фиксируем такую r, скармливаем ее в качестве совета машине типа P/poly — и дело сделано!

Итак, мы увидели простую связь между случайностью и неоднородностью. Прежде чем переходить к глубокой связи, позвольте мне сделать два замечания.

1. Даже если P ≠ NP, вас может заинтересовать, могут ли NP-полные задачи решаться за вероятностное полиномиальное время. Иными словами, входит ли NP в BPP? Понятно, что мы уже можем сказать кое-что конкретное по этому поводу. Если NP ⊆ BPP, то, разумеется, NP ⊂ P/poly (поскольку BPP ⊂ P/poly). Но это означает, что PH схлопывается по теореме Карпа — Липтона. Так что если вы верите, что полиномиальная иерархия бесконечна, то вы верите также, что NP-полные задачи не имеют эффективного решения рандомизированными алгоритмами.

2. Если неоднородность может моделировать случайность, то не может ли она также моделировать квантовость? Иными словами, верно ли, что BQP ⊂ P/poly? Вообще-то мы не знаем, но считается, что скорее всего да. Доказательство Адлемана (что BPP входит в P/poly) полностью рассыплется, конечно, если заменить BPP на BQP. Но это ставит интересный вопрос: а почему оно рассыплется? В чем принципиальная разница между квантовой теорией и классической теорией вероятностей, заставляющая это доказательство работать в одном случае, но не в другом? Я оставлю этот вопрос вам в качестве упражнения.

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

• Очевидно, что проверка на простоту входит в co-NP.

• В 1975 г. Пратт показал, что она входит в NP.

• В 1977 г. Соловей, Штрассен и Рабин показали, что она входит в co-RP.

• В 1992 г. Адлеман и Хуанг показали, что она входит в ZPP.

• В 2002 г. Аграваль, Кайал и Саксена показали, что она входит в P.

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

Опять же мы не знаем ответа на этот вопрос. Обычно, если мы не знаем, равны ли два класса сложности, «по умолчанию» они предполагаются различными. Так было и с P и BPP — зловещая музыка — до последнего времени. Однако в последние полтора десятка лет всё новые появляющиеся свидетельства убедили почти всех нас в том, что P = BPP. Мы не можем здесь сколько-нибудь глубоко разобрать эти свидетельства. Но позвольте мне процитировать одну теорему, просто чтобы показать вам, на что это похоже.

Теорема (Импальяццо — Вигдерсон, 1997)[39]. Пусть существует задача, решаемая за экспоненциальное время и не решаемая за субэкспоненциальное время даже при помощи строки совета субэкспоненциального размера. Тогда P = BPP.

Обратите внимание, как эта теорема связывает дерандомизацию с неоднородностью и, в частности, с доказыванием того, что определенные задачи трудны для неоднородных алгоритмов. Предположение, безусловно, представляется правдоподобным. С нашей сегодняшней точки зрения вывод (что P = BPP) также представляется правдоподобным. И все же впечатление таково, что они не имеют никакого отношения друг к другу. Так что про эту теорему можно было бы сказать: «Если ослы умеют кричать по-ослиному, то свиньи умеют хрюкать».

Откуда берется эта связь между случайностью и неоднородностью? Она исходит из теории генераторов псевдослучайных последовательностей. Мы познакомимся с псевдослучайными генераторами гораздо подробнее в следующей главе, когда будем говорить о криптографии. Но в основе своей псевдослучайный генератор — это всего лишь функция, принимающая на вход короткую строку (называемую зерном) и выдающая на выходе длинную строку таким образом, что если зерно случайно, то выходная строка выглядит случайной. Очевидно, выход не может быть случайным, поскольку в нем недостаточно энтропии: если зерно имеет длину k бит, то возможных выходных строк может быть лишь 2^k, независимо от их длины. Однако мы хотим лишь, чтобы никакой алгоритм полиномиального времени не мог успешно отличить выход псевдослучайного генератора от «настоящей» случайности. Разумеется, нам также хотелось бы, чтобы функция, превращающая зерно в выходную последовательность, была вычислима за полиномиальное время.

Уже в 1982 г. Энди Яо понял, что если бы можно было создать «достаточно хороший» псевдослучайный генератор, то можно было бы и доказать, что P = BPP. Почему? Ну предположим, что для любого целого k у вас имеется способ растянуть O(log n) — битное зерно в n-битную выходную псевдослучайную последовательность за полиномиальное время таким способом, что никакой алгоритм, выполняющийся за время n^k, не мог бы успешно отличить ее от истинно случайной последовательности. И предположим, у вас есть BPP-машина, работающая за время n^k. В таком случае вы можете просто сделать цикл по всем возможным зернам (которых существует лишь полиномиальное количество), скормить соответствующие выходные данные BPP-машине, а затем выдать в качестве результата ответ, составивший большинство. Вероятность того, что BPP-машина принимает, получив на вход псевдослучайную строку, должна быть примерно равна вероятности того, что она принимает, получив на вход по-настоящему случайную строку, поскольку иначе машина легко отличит случайные строки от псевдослучайных, вопреки нашему предположению!

Но какова во всем этом роль неоднородности? Вот в чем дело: кроме случайной (или псевдослучайной) строки, BPP-машина получает входную строку x. И нам нужно, чтобы дерандомизация работала для всех x. Но это означает, что для целей дерандомизации мы должны думать об x как о строке совета, исходящей от некоего сверхразумного советчика с единственной целью замаскировать псевдослучайный генератор. Понимаете, поэтому-то нам и нужна была задача, трудная даже при наличии совета: нам нужно построить генератор псевдослучайной последовательности, неотличимой от случайной даже в присутствии «советчика» x.

Подведем итоги: если бы мы могли доказать, что определенные задачи достаточно трудны для неоднородных алгоритмов, то мы доказали бы, что P = BPP.

Это ведет нас к третьему различию между BPP и BQP: если большинство специалистов верит, что P = BPP, то опять же большинство определенно не верит, что P = BQP. (В самом деле, мы не можем в это верить, если мы верим, что разложение на простые множители — трудная задача для классических компьютеров.) У нас нет программы «деквантизации», которой можно было бы приписать хотя бы малую долю успеха программы дерандомизации. Опять же создается впечатление, что между квантовой теорией и классической теорией вероятностей существует принципиальная разница, которая позволяет некоторым идеям (таким как идеи Сипсера, Гача и Лаутемана, Адлемана, Импальяццо — Вигдерсона) работать для второй, но не для первой.

Кстати говоря, Кабанец и Импальяццо[40] (и другие) сумели продемонстрировать нечто обратное — в определенном смысле — теоремам дерандомизации. Они показали, что если мы хотим доказать, что P = BPP, то нам придется доказать, что определенные задачи трудны для неоднородных алгоритмов. Это можно воспринимать как своеобразное объяснение причины, по которой никому еще не удалось доказать, P = BPP, хотя это и предполагается. Говоря точнее, дело в том, что если вы хотите доказать, P = BPP, то вам придется доказывать, что определенные задачи трудны, а если вы хотите доказать, что эти задачи трудны, то вы (по крайней мере косвенно) должны будете разбираться с вопросом о P и NP. В теории вычислительной сложности едва ли не любой вопрос в конце концов сходится к проблеме P и NP.