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

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

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

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

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

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

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

Живой уголок

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

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

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

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

Разумеется, P содержится в PSPACE. Я утверждаю также, что PSPACE содержится в EXP. Почему? Ну конечно же: машина с nk бит памяти может побывать в 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? Ведь Бог не мог быть настолько великодушен, чтобы наделить нас столь экстравагантными возможностями! Ведь физическая интуиция говорит нам, что поиск посредством грубой силы неизбежен! (Леонид Левин говорил