Пришла пора встретиться с самыми базовыми кассами сложности — агнцами и козлищами нашего Зоопарка cложности.

• P есть класс задач, решаемых машиной Тьюринга за полиномиальное время. Иными словами, P есть объединение классов TIME(n^k) по всем положительным целым k. (Обратите внимание: под «задачей» мы всегда будем подразумевать задачу разрешимости — задачу, где входные данные представляют собой n-битные строки, а ответом может быть «да» или «нет».)

• PSPACE есть класс задач, решаемых с использованием полиномиального объема памяти (но без ограничения по времени). Иными словами, это объединение классов SPACE(n^k) по всем целым k.

• EXP есть класс задач, решаемых за экспоненциальное время. Иными словами, это объединение TIME(2ⁿ^k) по всем целым k.

Разумеется, P содержится в PSPACE. Я утверждаю также, что PSPACE содержится в EXP. Почему? Ну конечно же: машина с n^k бит памяти может побывать в 2ⁿ^k различных конфигураций, прежде чем либо остановится, либо перейдет в бесконечный цикл.

Далее, NP есть класс задач, для которых, если ответ «да», то существует полиномиального размера доказательство этого, которое вы можете проверить за полиномиальное время. (Если вам интересно, сокращение NP означает «недетерминированный полиномиальный».) Я мог бы дать больше технических подробностей, но проще всего привести пример: скажем, я даю вам 10000-значное число и спрашиваю, есть ли у него делитель, заканчивающийся на 3. Ну, в принципе, поиск ответа на этот вопрос может занять долгое-долгое времяТМ. Но если ваш аспирант найдет для вас такой делитель, то вы сможете с легкостью проверить полученный результат: не обязательно доверять в этом смысле аспиранту (а это всегда плюс).

Я утверждаю, что NP содержится в PSPACE. Почему? А вот почему: в полиномиальном объеме памяти вы можете обойти все возможные nk-битные доказательства и проверить их одно за другим. Если ответ «да», то одно из доказательств сработает, а если ответ «нет», то не сработает ни одно из них.

Разумеется, P содержится в NP: если вы можете ответить на вопрос сами, то кто-то еще может убедить вас в том, что ответ «да» (если, конечно, он на самом деле «да»), вообще ничего вам не говоря.

Конечно, возникает вопрос, а не равны ли P и NP. Иными словами, если вы можете эффективно признать ответ, то не можете ли вы также эффективно найти его? Возможно, вам уже приходилось слышать об этом вопросе.

Что я могу сказать в общем о соотношении между P и NP? Этот вопрос часто и с удовольствием описывают как «вероятно, центральную нерешенную задачу теоретической информатики». Это смешное преуменьшение. Проблема P и NP — один из глубочайших вопросов, которые когда-либо задавали себе человеческие существа.

И не только: это одна из семи задач, за решение которых Математический институт имени Клэя[30] обещал по миллиону долларов! Какая честь! Представьте: наши друзья-математики решили, что проблема «P и NP» не менее важна, чем гипотеза Ходжа или даже существование и гладкость решений уравнений Навье — Стокса! (Очевидно, ее не собирались включать в этот достойный список, пока не опросили народ и не убедились в том, что она достаточно важна.)

Измерить важность проблемы «P и NP» можно, к примеру, так. Если бы задачи класса NP были разрешимы, то математическое творчество можно было бы автоматизировать. Способность проверить доказательство влекла бы за собой способность найти доказательство. Любой сегодняшний планшет или древний компьютер обладал бы мыслительной мощью Архимеда или Гаусса. Просто запрограммировав свой компьютер и запустив программу, вы, вероятно, могли бы немедленно решить не только проблему «P и NP», но и остальные шесть «задач тысячелетия». (Или пять, поскольку гипотеза Пуанкаре уже доказана.)

Но если дело обстоит так, то почему не очевидно, что P не равно NP? Ведь Бог не мог быть настолько великодушен, чтобы наделить нас столь экстравагантными возможностями! Ведь физическая интуиция говорит нам, что поиск посредством грубой силы неизбежен! (Леонид Левин говорил мне, что Фейнмана — короля или, быть может, придворного шута физической интуиции — трудно было убедить даже в том, что «P и NP» — нерешенная проблема!)

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

Допустим, вы получили N-значное число, но вы не хотите раскладывать его на множители, а хотите всего лишь узнать, простое это число или составное.

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

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

Разумеется, все это прекрасные примеры тех экспоненциально сложных NP-задач, о которых мы ведем речь! Разумеется, решать их тоже нужно грубой силой, то есть перебором!

Только на самом деле это не так. Оказывается, для всех этих задач имеются хитрые алгоритмы, позволяющие решать их за полиномиальное время! Главный вызов, с которым сталкивается любое доказательство P ≠ NP, — это необходимость отделить по-настоящему сложные NP-задачи от тех, которые только кажутся сложными. Я сейчас не просто излагаю некую философскую истину. На протяжении многих лет были предложены десятки предполагаемых доказательств неравенства P ≠ NP, но почти все их можно было бы отвергнуть практически с порога по той простой причине, что если бы они работали, то все те алгоритмы с полиномиальным временем, о существовании которых нам достоверно известно, были бы запрещены.

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

Оказывается, мы можем сказать кое-что гораздо более интересное, чем это. Мы можем сказать, что почти все «сложные» задачи представляют собой одну и ту же «сложную» задачу в разных обличьях — в том смысле, что если бы у нас был полиномиальный алгоритм для любой из них, то у нас были бы полиномиальные алгоритмы и для всех остальных. Это — главный результат теории NP-полноты, которую создали в начале 1970-х гг. Кук, Карп и Левин.

В общем, так: мы определяем задачу B как «NP-трудную», если любая NP-задача может быть эффективно сведена к B. Что, скажите на милость, это означает? Это означает, что если бы у нас был оракул, способный мгновенно решить задачу B, то мы могли бы решить любую NP задачу за полиномиальное время.

Так мы приходим к понятию редукции, или сведения, которое называется сведением по Куку. Существует также более слабое понятие сведения, называемое сведением по Карпу. В случае сведения по Карпу задачи A к задаче B мы настаиваем, что должен существовать алгоритм с полиномиальным временем, превращающий любой пример A в пример B, который имеет такой же ответ.

В чем же разница между Куком и Карпом?

Вот в чем: если речь идет о сведении по Куку, то при решении задачи A нам приходится вызывать оракул для задачи B более одного раза. Мы можем даже вызывать оракул адаптивно, то есть так, что каждый его вызов зависит от исхода предыдущих вызовов. Сведение по Карпу слабее в том смысле, что мы не позволяем себе подобных вольностей. Удивительно, но факт: почти все известные нам случаи сведения — это сведения по Карпу. На практике редко возникает нужда в инструменте такой мощи, как сведение по Куку.

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

Я утверждаю, что это очевидно. Почему?

Ну, рассмотрим следующую задачу, называемую «Дык»: нам дана машина Тьюринга полиномиального времени M, и мы хотим знать, существует ли входная строка из n^k бит, которую M принимает[31]. Я утверждаю, что любой случай любой NP-задачи может быть превращен за полиномиальное время в пример для «Дык» с тем же ответом. Почему? Дык! Потому что именно это означает принадлежность задачи к NP!

Открытие Кука, Карпа и Левина состояло не в том, что NP-полные задачи существуют, — это очевидно, — но скорее в том, что многие естественные задачи являются NP-полными.

Королем этих естественных NP-полных задач является задача выполнимости логических формул 3-SAT. (Откуда я знаю, что это и правда король? Ну как же, об этой задаче рассказывали в телешоу NUMB3RS.) В этой задаче нам дается n булевых переменных x₁, …, x_n, а также формула — некий набор логических ограничений, называемых предложениями, в каждом из которых фигурирует не более трех переменных:

x ₂ или x ₅ или не ( x ₆)

не ( x ₂) или x ₄

не ( x ₄) или не ( x ₅) или x ₆

…

Вопрос в том, существует ли какой-нибудь способ задать переменным x₁, …, xn значения «истина» или «ложь» так, чтобы все предложения формулы оказались выполнены (то есть значение каждого из них было «истина»).

Очевидно, что задача 3-SAT относится к классу NP. Почему? Верно: потому что если кто-то даст вам работающий комплект x₁, …, x_n, то проверить факт его пригодности несложно!

Наша цель — доказать, что 3-SAT является NP-полной. Что для этого требуется? Ну, необходимо показать, что, если у нас есть оракул для 3-SAT, мы можем с его помощью решить не только 3-SAT за полиномиальное время, но и вообще любую NP-задачу. Кажется, очень непросто! Однако чуть позже, задним числом, вы увидите, что делается это почти тривиально.

Доказательство складывается из двух этапов. Этап 1 — показать, что если бы мы могли решить 3-SAT, то мы могли бы решить и более «общую» задачу выполнимости для булевой схемы (CircuitSAT). Этап 2 — показать, что, имея возможность решить CircuitSAT, мы могли бы решить любую NP задачу.

В CircuitSAT нам задается булева схема и… погодите-ка. Инженеры, слушайте внимательно: в информатике в «схеме» никогда не бывает ни контуров, ни циклов! В ней также нет резисторов и диодов и вообще никаких таких странных вещей. Для нас схема — это просто объект, где для начала у вас есть n булевых переменных x₁, …, x_n, а затем вы можете сколь угодно долго определять новые переменные, которые получаются из уже определенных посредством операций и, или и не. Примерно так:

x_{n +1}:= x ₃ или x_n

x_{n +2}:= не ( x_{n +1})

x_{n +3}:= x ₁ и x_{n +2}

…

Последнюю переменную в списке мы назначаем «выходом» схемы. Тогда наша цель в задаче CircuitSAT — решить, существует ли набор x₁, …, x_n, такой что на выходе схемы получается «истина».

Я утверждаю, что если бы мы могли решить 3-SAT, то мы могли бы решить и задачу CircuitSAT. Почему?

Потому что все, что нам нужно сделать, — это отметить, что каждая реализация CircuitSAT есть на самом деле замаскированная реализация 3-SAT! Всякий раз, когда мы проделываем операции и, или или не, мы соотносим одну новую переменную с одной или двумя старыми. И любое такое соотношение может быть выражено набором предложений, в каждом из которых задействовано не более трех переменных. Так, к примеру,

x_{n +1}:= x ₃ или x_n

превращается в

x_{n +1} или не ( x ₃)

x_{n +1} или не ( x_n )

не (x_n+1) илиx₃ илиx_n.

Итак, этап 1 пройден. На этапе 2 нужно показать, что если мы можем решить CircuitSAT, то можем решить любую NP-задачу.

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

Далее, при наличии этой машины Тьюринга, наша цель — создать схему, которая «имитировала» бы M. Иными словами, мы хотим, чтобы набор входных переменных, при котором схема дает на выходе «истину», существовал в том и только том случае, если существует строка w, которую M принимает.

Как этого добиться? Просто: возьмем и определим весь набор переменных целиком! В нем у нас будет переменная, равная «истине» в том и только том случае, если 37-й бит ленты машины M принимает значение 1 на 42-м шаге по времени. Еще у нас будет переменная, равная «истине» в том и только том случае, если 14-й бит принимает значение 1 на 52-м шаге по времени. А еще у нас будет переменная, которая равна «истине» в том и только том случае, если считывающая головка M будет находиться в 15-м внутреннем состоянии и на 74-й позиции ленты на 33-м шаге по времени. Ну, вы поняли идею.

Затем, записав всю эту кучу переменных, мы записываем также хренову тучу логических соотношений между ними. Если 17-й бит ленты равен 0 на 22-м шаге по времени, а считывающая головка в это время и близко не подходит к 17-му биту, то этот самый 17-й бит и на 23-м шаге по времени останется равным 0. Если считывающая головка на 44-м шаге по времени находится во внутреннем состоянии 5 и считывает на этом шаге 1, а внутреннее состояние 5 по считывании 1 переходит во внутреннее состояние 7, то на 45-м шаге по времени считывающая головка будет находиться во внутреннем состоянии 7. И так далее, и тому подобное. Единственные переменные, на которые не накладываются ограничения, — это те, что составляют строку w на первом шаге по времени.

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

Мы только что доказали знаменитую теорему Кука — Левина: задача 3-SAT является NP-полной. Эту теорему можно считать «точкой инфицирования» вирусом NP-полноты. С того момента, как она была доказана, вирус распространился на тысячи других задач. Вот что я имею в виду: если вы хотите доказать, что ваша любимая задача является NP-полной, то все, что вам нужно сделать, — это доказать, что она столь же трудна, как какая-то другая задача, принадлежность которой к NP-полным уже доказана. (Вообще говоря, вам также нужно доказать, что она принадлежит классу NP, но это, как правило, тривиально.) Так что здесь наблюдается эффект «деньги к деньгам»: чем для большего числа задач доказана NP-полнота, тем проще ввести в этот клуб новую задачу. В самом деле, к 1980-м или 1990-м гг. доказывание NP-полноты задач стало такой рутиной, и это так хорошо научились делать, что (за редкими исключениями) две главных конференции по вычислительной сложности STOC и FOCS перестали публиковать новые доказательства NP-полноты.

Я приведу вам крохотную выборку задач, NP-полнота которых была доказана в самом-самом начале.

• Раскраска карты. На заданной карте можно ли раскрасить каждую страну в красный, зеленый или синий цвет таким образом, чтобы никакие две соседние страны не оказались одного цвета? (Интересно, что если разрешены только две краски, то нетрудно решить, возможна ли такая раскраска, — почему? С другой стороны, если разрешены четыре краски, то это возможно всегда, по крайней мере в случае, когда карта рисуется на плоскости, — об этом говорит знаменитая теорема о четырех красках. Так что и в этом случае задача решается просто. Только в случае трех красок задача становится NP-полной.)

• Компания. Если имеется некоторое множество из N старшеклассников, с которыми некто и данные о том, кто из старшеклассников с кем готов сидеть в школьной столовой за одним столом, то найдется ли компания из N/3 старшеклассников, готовых сидеть всей компанией за одним большим столом?

• Упаковка. Если имеется набор коробок заданных размеров, то можно ли уложить их в багажник вашего автомобиля?

И т. п., и т. п.

Повторю еще раз: хотя эти задачи могут показаться совершенно не связанными между собой, на самом деле это одна и та же задача в разном облачении. Если любая из них имеет эффективное решение, то все они имеют такое решение, и P = NP. Если любая из них не имеет эффективного решения, то ни одна из них такого решения не имеет, и P ≠ NP. Чтобы доказать P = NP, достаточно показать, что какая-то NP-полная задача (не важно, какая именно) имеет эффективное решение. Чтобы доказать P ≠ NP, достаточно показать, что какая-то NP-полная задача не имеет эффективного решения. Один за всех и все за одного.

Итак, существуют, с одной стороны, P-задачи, а с другой — NP-полные задачи. А есть ли что-нибудь в промежутке? (Вам следовало бы уже привыкнуть к подобным «промежуточным» вопросам — мы видели их и в теории множеств, и в теории вычислимости!)

Если P = NP, то NP-полные задачи являются одновременно и P-задачами, так что ответ, очевидно, нет.

Но что если P ≠ NP? В этом случае красивый вывод, известный как теорема Ладнера, говорит, что между P и NP-полными должны существовать «промежуточные» задачи, иными словами, задачи, принадлежащие NP, но не являющиеся ни NP-полными, ни решаемыми за полиномиальное время.

Как можно было бы сконструировать такую промежуточную задачу? Я предложу идею. Первым делом нужно определить некоторую чрезвычайно медленно растущую функцию t. Затем для заданной 3-SAT реализации F размера n задача будет состоять в том, чтобы установить, удовлетворены ли сразу два условия: F выполнима и t(n) нечетна. Иными словами: если t(n) нечетна, то ответ дает решение задачи 3-SAT, тогда как если t(n) четна, то результат уже «нет».

Если вы задумались о том, чем мы занимаемся, то мы чередуем длинные интервалы NP-полной задачи с длинными интервалами пустоты! Интуитивно представляется, что каждый интервал 3-SAT должен устранять еще один алгоритм полиномиального времени для нашей задачи, поскольку мы используем допущение, что P ≠ NP. Аналогично каждый пустой интервал должен исключать очередное сведение NP-полноты, где мы вновь используем допущение, что P ≠ NP. Это гарантирует, что задача не относится ни к P, ни к NP-полным. Основной технический фокус здесь — заставить интервалы удлиняться с экспоненциальной скоростью. Получив на вход сигнал размера n, мы можем смоделировать весь итеративный процесс вплоть до n за время, полиномиальное по n. Это гарантирует, что наша задача по-прежнему относится к NP.

Помимо P и NP, есть еще один крупный класс сложности — co-NP, «дополнение» к NP. Задача относится к co-NP, если ответ «нет» может быть проверен за полиномиальное время. У любой NP-полной задачи имеется соответствующая ей co-NP-полная задача. Здесь мы имеем невыполнимость, нераскрашиваемость карты и т. п.

Хорошо, но почему вообще кому-то должно прийти в голову определять такую глупость? Потому что тогда мы можем задать новый вопрос: равны ли NP и co-NP? Иными словами, если булева формула невыполнима, существует ли по крайней мере короткое доказательство того, что она невыполнима, даже если нахождение этого доказательства потребовало бы экспоненциального времени? Ответ, опять же, состоит в том, что мы этого не знаем.

Конечно, если P = NP, то NP = co-NP. (Почему?) С другой стороны, в другом направлении ничего не известно: возможно, P ≠ NP, но при этом все же NP = co-NP. Так что если доказательство P ≠ NP покажется вам слишком простым, можете попробовать вместо этого доказать NP ≠ co-NP!

Пора, кажется, упомянуть еще один, особый класс сложности — класс, который мы, специалисты по квантовым вычислениям, знаем и любим: NP ∩ co-NP.

Это класс, для которого или ответ «да», или ответ «нет» имеет эффективно проверяемое доказательство. В качестве примера рассмотрим задачу разложения целого числа на простые множители. За свою жизнь я встречал, должно быть, по крайней мере два десятка людей, которые «знали», что задача разложения относится к NP-полным и потому алгоритм Шора — а он позволяет нам проводить факторизацию на квантовом компьютере — позволяет нам также решать на квантовом компьютере NP-полные задачи. Очень часто такие люди чрезвычайно уверены в своем «знании».

Прежде чем мы станем разбираться в возможной NP-полноте разложения на простые множители, позвольте мне по крайней мере объяснить, почему я считаю, что задача разложения не относится к классу P. Могу ли я сказать, что никто не может эффективно решить ее на практике? Хотя это не слишком хороший аргумент, все, безусловно, рассчитывают, что эта задача не относится к P. Следует признать, что у нас нет столь же серьезных причин считать, что факторизация не относится к P, какие есть считать, что P ≠ NP. Мнение о том, что факторизация, может быть, все же относится к P и мы просто недостаточно знаем о теории чисел, чтобы доказать это, можно даже счесть почти респектабельным. Если вы потратите две секунды, чтобы обдумать это, то поймете, что задача разложения на простые множители имеет глубокие отличия от известных NP-полных задач. Если я дам вам булеву формулу, то у нее может вообще не оказаться удовлетворяющих всем условиям входных данных, дающих на выходе истину, может оказаться один набор таких данных, а может оказаться их 10 триллионов. Вы просто не можете знать этого заранее. Но если я дам вам 5000-значное целое число, то вы, вероятно, не сможете сразу сказать, на какие множители оно раскладывается, но будете точно знать, что оно имеет одно и только одно разложение. (Насколько я помню, парень по имени Евклид доказал это довольно давно.) Уже это говорит нам, что разложение на простые множители — в чем-то «особая» задача: в отличие от того, что нам вроде бы известно о NP-полных задачах, факторизация обладает некоей структурой, которую алгоритмы могут попытаться использовать. И алгоритмы действительно ее используют: нам известен классический алгоритм под названием «решето числового поля», позволяющий разложить n-значное целое число на множители примерно за шагов, а не за ~2^n/2 шагов, которые потребовались бы для перебора всех возможных делителей. (Кстати, а почему только ~2^n/2 шагов, а не ~2ⁿ?) И, разумеется, нам известен алгоритм Шора, позволяющий разложить n-битное целое число за ~ n² шагов на квантовом компьютере, то есть за квантовое полиномиальное время. Вопреки популярному мнению, мы не знаем квантового алгоритма, позволяющего решать NP-полные задачи за полиномиальное время. Если бы такой алгоритм существовал, то он наверняка резко отличался бы от алгоритма Шора.

Но можем ли мы указать конкретно, чем именно разложение на простые множители отличается от известных NP-полных задач в терминах теории вычислительной сложности? Да, можем. Во-первых, чтобы превратить разложение на множители в проблему разрешимости (да-или-нет), нам придется задавать примерно такие вопросы: если дано положительное целое число N, то имеет ли N простой множитель с последней цифрой 7? Я утверждаю, что эта задача относится не просто к NP, но к NP ∩ co-NP. Почему? Ну, предположим, кто-то дал вам вариант разложения N на простые множители. Разложение существует только одно. Поэтому если в нем имеется простой множитель с последней цифрой 7, это можно проверить, и если такого множителя нет, это можно проверить тоже.

Вы можете сказать: «Но откуда мне знать, что мне на самом деле дали разложение на простые множители? Конечно, если кто-то дает мне набор чисел, я могу убедиться в том, что при перемножении они дают 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, и именно столько памяти нам потребуется, чтобы записать в самом начале список предпочтений.

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

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

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

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

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