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

Дополнительная литература

В следующих нескольких главах мы продолжим разбор теории вычислительной сложности. Однако для тех читателей, которых невозможно насытить информацией и которые действительно хотят глубоко разобраться в этом предмете, назову несколько своих любимых книг: Computational Complexity by Christos Papadimitriou (Addison-Wesley, 1994); Computational Complexity: A Modern Approach, by Sanjeev Arora and Boaz Barak (Cambridge University Press, 2009); и The Nature of Computation, by Cristopher Moore and Stephan Mertens (Oxford University Press, 2011).

Загадка 1 из предыдущей главы

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

Ответ: да, такие программы существуют. Более того, проходят даже конкурсы на то, кто напишет самую короткую самораспечатывающуюся программу. На международном конкурсе IOCCC (International Obfuscated C Code Contest)[28]28
  http://www.ioccc.org/


[Закрыть] несколько лет назад победила необычайно короткая программа. Догадайтесь, сколько в ней было символов: 30? 10? 5?

В победившей программе был ровно нуль знаков. (Подумайте об этом!) Правда, пустой файл нельзя все же назвать по-настоящему кошерной программой на языке C, но, судя по всему, некоторые компиляторы готовы скомпилировать его в программу, которая не будет ничего делать.

Хорошо, хорошо, но что если мы хотим получить нетривиальную программу, которая печатает сама себя? В этом случае стандартный фокус состоит в том, чтобы проделать примерно следующее (вы можете самостоятельно перевести это на свой любимый язык программирования):

Напечатать следующее дважды, второй раз в кавычках.

"Напечатать следующее дважды, второй раз в кавычках."

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

Эту идею придумал фон Нейман в самом начале 1950-х. Вскоре после этого два человека (мне кажется, их звали Крик и Уотсон) нашли физическую систему, которая на самом деле следует этим правилам. Мы с вами, вместе со всеми живыми существами Земли, по существу, представляем собой живые компьютерные программы такого содержания:

Сделать ребенка, который действует по нижеследующей инструкции, а также содержит копию этой инструкции в своих репродуктивных органах.

"Сделать ребенка, который действует по нижеследующей инструкции, а также содержит копию этой инструкции в своих репродуктивных органах."

Загадка 2 из предыдущей главы

Если бы вода не была H₂O, была бы она по-прежнему водой?

Ага, это на самом деле не есть хорошо определенный вопрос: все его содержание сводится к тому, что мы подразумеваем под словом вода. Задает ли вода «условия»: если вещество x прозрачное и мокрое, годится для питья и не имеет вкуса, образует при замерзании лед и т. п., то x и есть вода? При такой постановке вопроса само понятие воды можно определить, сидя в кресле, путем перечисления необходимых и достаточных условий того, чтобы нечто можно было считать водой. Затем мы выходим наружу – и все, что удовлетворяет нашим условиям, является водой по определению. Именно так считали Фреге и Рассел; в этом случае подразумевается, что все, что обладает «интуитивно понятными» свойствами воды, водой и является, вне зависимости от того, H₂O это или не H₂O.

Другой подход к этому вопросу, ставший визитной карточкой Саула Крипке[29]29
  См: Saul Kripke, Naming and Necessity, Wiley-Blackwell, 1991 (reprint edition).


[Закрыть], заключается в том, что слово вода «жестко обозначает» вполне конкретное вещество (H₂O). С этой позиции мы сегодня можем точно сказать, что, когда древние греки или вавилоняне говорили о воде, они на самом деле имели в виду H₂O, хотя и не понимали этого. Интересно, что в этом случае «вода = H₂O» – необходимая истина, открытая путем эмпирических наблюдений. Нечто с теми же интуитивными свойствами, как у воды, но с другой химической структурой уже не было бы водой.

Крипке утверждает, что если принять точку зрения, предполагающую «жесткое обозначение», то одно из ее следствий будет связано с проблемой взаимоотношений сознания и тела. Идея в следующем: мечта редукциониста – объяснить сознание в терминах нейронных импульсов, точно так же, как наука объяснила воду как вещество с химической формулой H₂O. Но Крипке говорит, что аналогия между двумя ситуациями неполна. В случае воды мы можем по крайней мере говорить осмысленно о какой-то гипотетической субстанции, которая выглядит и ощущается как вода, на вкус как вода и т. п., но имеет формулу, отличную от H₂O, и потому не является водой. Но предположим, что мы обнаружили бы, что боль всегда связана со срабатыванием определенных нервов, названных C-волокнами. Могли бы мы тогда сказать, что боль – это и есть срабатывание C-волокон? Если бы нечто ощущалось как боль, но имело иное нейробиологическое происхождение, сказали бы мы, что оно ощущается как боль, но болью не является? Вероятно, нет. Все, что ощущается как боль, и есть боль, по определению! Из-за этой разницы Крипке считает, что мы не можем говорить, что боль «есть» срабатывание C-волокон, в том же смысле, в каком мы можем говорить, что вода «есть» H₂O.

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

6. P, NP и все-все-все

Мы уже видели, что если хотим добиться чего-то в исследовании вычислительной сложности, то нам следует говорить об асимптотическом поведении: не о том, какие задачи могут быть решены за 10000 шагов, а о том, для каких задач примеры размера n могут быть решены за cn² шагов при n, стремящемся к бесконечности. Мы видели TIME (f(n)) – класс всех задач, решаемых за O (f(n)) шагов, и SPACE (f(n)) – класс всех задач, решаемых с использованием O (f(n)) бит памяти.

Но если мы действительно хотим продвинуться дальше, полезно принять еще более грубую модель, в которой различаются полиномиальное и экспоненциальное время, но не различаются времена O(n²) и O(n³). С такой позиции мы будем рассматривать всякую полиномиальную оценку как «быструю», а всякую экспоненциальную оценку – как «медленную».

Я понимаю, что мне сразу же возразят: что, если проблема решаема за полиномиальное время, но полином получается 50000-ного порядка, то есть с n⁵⁰⁰⁰⁰? Или что, если задача занимает экспоненциальное время, но экспонента имеет вид 1,00000001ⁿ? Мой ответ в высшей степени прагматичен: если подобные случаи будут регулярно возникать в практических задачах, то, скорее всего, мы использовали неверную абстракцию. Но до сих пор не было оснований считать, что мы используем неверный подход. Среди крупных задач, решаемых за полиномиальное время, – а это распознавание, линейное программирование, проверка на простоту и т. п. – большая часть и правда имеет практически реализуемые алгоритмы. А из крупных задач, решение которых, по нашему мнению, требует экспоненциального времени, – доказательство теорем, минимизация схемы и т. п. – большинство на самом деле не имеет практичных алгоритмов. Итак, перед вами эмпирический скелет, на котором держится и наш жир, и наши мускулы.

Живой уголок

Пришла пора встретиться с самыми базовыми кассами сложности – агнцами и козлищами нашего Зоопарка 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]30
  См.: http://www.claymath.org/millennium/


[Закрыть] обещал по миллиону долларов! Какая честь! Представьте: наши друзья-математики решили, что проблема «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]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, это можно проверить, и если такого множителя нет, это можно проверить тоже.