Текст книги "Квантовые вычисления со времен Демокрита"

Вы можете сказать: «Но откуда мне знать, что мне на самом деле дали разложение на простые множители? Конечно, если кто-то дает мне набор чисел, я могу убедиться в том, что при перемножении они дают N, но откуда мне знать, что все они простые?» Для этого вам придется принять на веру кое-что, о чем я уже говорил: что если вы хотите просто проверить, простое это число или составное, а не найти сами сомножители, то сделать это можно за полиномиальное время. О'кей, если вы с этим согласны, то задача разложения на простые множители относится к классу NP ∩ co-NP.

Из этого мы можем заключить, что если разложение на множители – NP-полная задача, то NP должен равняться co-NP. (Почему?) А поскольку мы не верим, что NP = co-NP, то можно считать это сильным доводом (хотя и не доказательством) в пользу того, что, несмотря на всех тех людей, о которых я вам рассказывал, факторизация не является NP-полной задачей. Если мы это принимаем, остается только два варианта: факторизация либо относится к классу P, либо является одной из тех «промежуточных» задач, чье существование гарантируется теоремой Ладнера. Большинство специалистов склоняется ко второму варианту, хотя и с меньшей уверенностью, чем наша уверенность в том, что P ≠ NP.

На самом деле может оказаться даже, что P = NP ∩ co-NP, но при этом все равно P ≠ NP. (Такой вариант подразумевал бы, что NP ≠ co-NP.) Так что если вам кажется слишком простым доказательство обоих утверждений – и P ≠ NP, и NP ≠ co-NP, то вашей следующей целью может стать доказательство утверждения P ≠ NP ∩ co-NP!

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

Обратите внимание, что вы можете представить любую реализацию NP-задачи в форме:

Существует ли n-битная строка X, такая, что A (X) = 1?

Здесь A – функция, вычислимая за полиномиальное время.

Аналогично вы можете представить любую задачу co-NP в форме:

Верно ли A (X) = 1 для любого X?

Но что произойдет, если добавить к этому еще один квантор, примерно так:

Существует ли X, такой, что A (X, Y) = 1 для любого Y?

Для любого X существует ли Y, такой, что A (X, Y) = 1?

Такие задачи приводят нас к двум новым классам сложности, которые называются Σ₂P и Π₂P соответственно. Π₂P – это «дополнение» к Σ₂P в том же смысле, в каком co-NP есть дополнение к NP. Кроме того, мы можем добавить и третий квантор:

Существует ли X, такой, что для любого Y существует Z, такой, что A (X, Y, Z) = 1?

Для любого X существует ли Y, такой, что для любого Z имеем A (X, Y, Z) = 1?

Это дает нам классы сложности Σ₃P и Π₃P соответственно. Должно быть очевидно, как обобщить это до Σ_kP и Π_kP для любого большего k. (На полях отмечу, что когда k = 1 мы получаем Σ₁P = NP и Π₁P = co-NP. Почему?) Затем, взяв объединение этих классов по всем положительным целым k, мы получаем полиномиальную иерархию PH.

Эта полиномиальная иерархия в самом деле представляет собой существенное обобщение NP и co-NP – в том смысле, что даже если бы у нас был оракул для NP-полных задач, совершенно неясно, как мы бы могли использовать его для решения, скажем, Σ₂P-задач. С другой стороны, я утверждаю (просто для того, чтобы еще усложнить ситуацию), что если P = NP, то вся полиномиальная иерархия схлопнется до одного P! Почему?

Верно: если P = NP, то мы могли бы взять наш алгоритм для решения NP-полных задач за полиномиальное время и модифицировать его так, чтобы он вызывал сам себя в качестве подпрограммы. И это позволило бы нам «сплющить PH паровым катком»: сначала смоделировать NP и co-NP, затем Σ₂P и Π₂P и т. п. по всей иерархии.

Подобно этому несложно доказать, что если NP = co-NP, то вся полиномиальная иерархия схлопнется до NP (или, иными словами, до co-NP). Если Σ₂P = Π₂P, то вся полиномиальная иерархия схлопнется до Σ₂P, и так далее. Если немного подумать, это дает нам целую бесконечную последовательность обобщений гипотезы P ≠ NP, таких, что каждую последующую доказать «труднее», чем предыдущую. Почему нас вообще интересуют эти обобщения? Потому что часто случается так, что при изучении некоторой гипотезы с условным именем Ля-ля мы не можем доказать, что Ля-ля верна, и не можем даже доказать, что если бы Ля-ля была неверна, то P был бы равен NP. Но – и в этом вся изюминка – мы можем доказать, что если бы Ля-ля была неверна, то полиномиальная иерархия схлопнулась бы до второго или третьего уровня. А это некоторый аргумент в пользу того, что Ля-ля все-таки верна.

В общем, добро пожаловать в теорию вычислительной сложности!

Я уже рассказывал о том, что многие задачи имеют неочевидные алгоритмы, выполнимые за полиномиальное время, и мне показалось, что следует дать вам хотя бы один пример. Давайте рассмотрим одну из простейших и элегантнейших задач во всей теоретической информатике – так называемую задачу о стабильном браке. Случалось вам видеть ее прежде? Не случалось?

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

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

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

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

Таким образом, наша цель как коллективной свахи состоит в том, чтобы найти стабильный способ переженить их всех с учетом заданных предпочтений мужчин и женщин.

Первый очевидный вопрос: всегда ли существует стабильный вариант распределения мужчин и женщин на пары? Как вы считаете? Да? Нет? Оказывается, такое распределение существует, но простейший способ доказать это – просто дать алгоритм его нахождения!

Давайте сосредоточимся на вопросе о том, как найти такой вариант. В целом существует N! способов распределения наших женихов и невест по парам. И надо надеяться, хотя бы ради наших потенциальных новобрачных, что нам не придется перебирать их все.

К счастью, действительно не придется. В начале 1960-х гг. Гейл и Шейпли придумали алгоритм полиномиального – более того, линейного – времени для решения этой задачи. Прелесть его в том, что он в точности соответствует варианту, который вы могли бы предложить, начитавшись викторианских любовных романов. Позже они обнаружили, что этот самый алгоритм уже используется с 1950-х гг., но не для организации массовых бракосочетаний, а для распределения студентов-медиков по больницам на интернатуру. Мало того, больницы и медицинские школы до сих пор пользуются одной из версий этого алгоритма.

Но вернемся к нашим мужчинам и женщинам. Если мы хотим переженить их всех при помощи алгоритма Гейла – Шейпли, то в качестве первого шага нам нужно нарушить симметрию между полами и решить: какой пол «делает предложение»? Поскольку дело происходило в начале 1960-х гг., можете сами представить, каким был ответ. Предложение всегда делали мужчины.

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

Первый вопрос: почему этот алгоритм завершается за линейное время?

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

Второй вопрос: почему, когда алгоритм завершает работу, все оказываются состоящими в браке?

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

Третий вопрос: почему распределение, рожденное этим алгоритмом, будет стабильным?

Верно: потому что если бы это было не так, то возникла бы одна семейная пара (скажем, Боб и Алиса) и другая семейная пара (скажем, Чарли и Ева), такие, что и Боб, и Ева предпочитают друг друга своим супругам. Но в таком случае Боб должен был сделать предложение Еве прежде, чем Алисе. И если Чарли тоже сделал предложение Еве, то Ева тоже сразу дала бы понять, что предпочитает Боба. Возникает противоречие.

В частности, мы показали, как и было обещано, что существует стабильное распределение на пары, а именно распределение, полученное посредством алгоритма Гейла – Шейпли.

Задачи

1. Мы видели, что задача 3-SAT относится к NP-полным. Напротив, оказывается, что задача 2-SAT – вариант, в котором в каждом предложении разрешены лишь две переменные, – решается за полиномиальное время. Объясните, почему.

2. Вспомним, что EXP – это класс задач, решаемых за экспоненциальное время. Можно определить также класс NEXP: класс задач, для которых ответ «да» может быть проверен за экспоненциальное время. Иными словами, NEXP для EXP то же самое, что NP для P. Далее, мы не знаем, верно ли P = NP, и не знаем также, верно ли EXP = NEXP. Но мы точно знаем, что если P = NP, то EXP = NEXP. Почему?

3. Покажите, что P не равняется SPACE(n) (множеству задач, решаемых с использованием линейного объема памяти). Подсказка: вам не нужно доказывать, что P не входит в SPACE(n) или что SPACE(n) не входит в P, нужно доказать только, что верно то или другое.

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

5. [Повышенной сложности.] Приведите в явном виде алгоритм, позволяющий найти входную строку (если таковая существует), для которой выполняется формула, и выполняемый за полиномиальное время, при условии, что P = NP. (Если формула невыполнима, ваш алгоритм может вести себя произвольным образом.) Иными словами, приведите алгоритм для задачи 4, который можно реализовать и выполнить прямо сейчас, без привлечения какой бы то ни было подпрограммы, которая, как вы полагаете, существует, но которую вы не в состоянии описать.

7. Случайность

В последних двух главах мы говорили о вычислительной сложности до начала 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]32
  W. R. Alford, A. Granville and C. Pomerance, There are infinitely many Carmichael numbers, Annals of Mathematics 2:139 (1994), 703–722. http://www.math.dartmouth.edu/∼carlp/PDF/paper95.pdf


[Закрыть] показали в 1994 г., что чисел-«притворщиков» существует бесконечно много.

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

Затем, лет десять назад, произошел прорыв, о котором вы, вероятно, слышали. Аграваль, Кайал и Саксена[33]33
  M. Agrawal, N. Kayal, and N. Saxena, PRIMES is in P, Annals of Mathematics 160:2 (2004), 781–793. http://www.cse.iitk.ac.in/users/manindra/algebra/primalityv6.pdf


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

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

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

Когда мы говорим о вероятностных вычислениях, скорее всего, речь идет об одном из следующих четырех классов сложности, которые Джон Гилл[34]34
  J. Gill, Computational Complexity of Probabilistic Turing Machines, SIAM Journal on Computing 6:4 (1977), 675–695.


[Закрыть] определил в работе, опубликованной в 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]35
  Исход президентских выборов в США в ноябре 2000 г. зависел от того, на чью сторону встанут выборщики от штата Флорида, а там количество проголосовавших за Альберта Гора и за Джорджа Буша (сына) различалось всего на несколько десятков голосов. На то, чтобы установить волю избирателей, потребовалось несколько недель, и половину Америки результат подсчета не убедил. – Прим. пер.


[Закрыть]! Там, где речь идет о 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 можно без труда уменьшить до такой степени, что она будет меньше вероятности попадания астероида в ваш компьютер. И этого достаточно для большинства приложений: скажем, для отслеживания доз облучения в больнице, для шифрования многомиллиардных банковских операций или для управления пусками ядерных ракет. Но как насчет доказывания теорем? В некоторых приложениях рисковать просто нельзя.