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

Ключевой момент здесь в том, что, хотя это очень большая куча переменных и отношений, это все же полиномиальная куча. Поэтому мы получаем полиномиального размера пример 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-полным и потому алгоритм Шора — а он позволяет нам проводить факторизацию на квантовом компьютере — позволяет нам также решать