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

Ну хорошо, мы, конечно, верим, что 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, и мы хотим знать, существует ли входная строка из nk бит, которую M принимает[31]. Я утверждаю, что любой случай любой NP-задачи может быть превращен за полиномиальное время в пример для «Дык» с тем же ответом. Почему? Дык! Потому что именно это означает принадлежность задачи к NP!

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

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

x 2 или x 5 или не ( x 6)