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

class="sup">3, … — список полиномиальных по времени машин Тьюринга. Кроме того, зафиксируем длину входной строки n. Я утверждаю, что существует булева функция f: {0, 1}n → {0, 1}, которую первым n машинам (M1,…, Mn) не удается вычислить даже при наличии любой nlog n-битной строки совета. Почему? Просто посчитаем: существует 22ⁿ булевых функций, но только n машин Тьюринга и строк совета. Поэтому выберите такую функцию f для каждого n; при этом каждую машину Mi, ждет неудача при всех длинах, за исключением конечного их числа. Вот и все, нам не потребовалось даже условие, что Mi работает полиномиальное время.

Почему для меня так важен совет? Во-первых, он появляется снова и снова, даже если нас, к примеру, интересуют лишь однородные вычисления. Даже если мы хотим узнать всего лишь, можно ли дерандомизировать BPP, оказывается, что и этот вопрос имеет отношение к совету. Так что совет очень тесно связан с остальными понятиями вычислительной сложности. По существу, можно считать, что алгоритм с советом ничем не отличается от бесконечной последовательности алгоритмов, точно как мы видели в случае теоремы ускорения Блума. Это всего лишь алгоритм, где по мере увеличения длины входной строки вам приходится использовать все новые идеи и добиваться все большего ускорения. Совет можно, в частности, рассматривать так.

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

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

Разумеется, все это время мы с вами танцевали вокруг настоящего вопроса: может ли совет помочь нам в решении задач, которые нас действительно интересуют, таких как NP-полные задачи? В частности, верно ли, что NP ⊂ P/poly? Интуитивно представляется, что вряд ли: булевых формул размера n экспоненциально много, так что если бы вы даже получили каким-то образом от Бога строку совета полиномиального размера, то как бы это помогло вам определить выполнимость больше чем крохотной части этих формул?

Но — и я уверен, что для вас это станет полнейшим шоком, — мы не можем доказать, что это невозможно. Правда, в данном случае у нашего невежества есть хорошее оправдание, поскольку если P = NP, то, очевидно, верно также и NP ⊂ P/poly. Но вот вопрос: если бы нам удалось доказать P ≠ NP, то доказали бы мы тем самым, что NP ⊄ P/poly? Иными словами, следует ли из NP ⊂ P/poly, что P = NP? Увы, мы не знаем ответа даже на этот вопрос.

Но, как и в случае с BPP и NP, ситуация не настолько неприятна, как кажется. Карпу и Липтону все же удалось доказать в 1982 г., что если NP ⊂ P/poly, то полиномиальная иерархия PH схлопывается до второго уровня (то есть до NPNP). Иными словами, если вы верите, что полиномиальная иерархия бесконечна, вы должны также верить, что NP-полные задачи не решаются эффективно неоднородными алгоритмами.

Эта теорема Карпа — Липтона — самый известный пример очень обширного класса результатов теории вычислительной сложности, класса, который описывают формулировкой «если бы ослы умели свистеть, то свиньи умели бы летать». Иными словами, если бы одна вещь, в истинность которой никто не верит, была бы истинна, то истинна была бы и другая вещь, в истинность которой тоже никто не верит! Интеллектуальный онанизм, говорите? Чепуха! Интересно здесь то, что обе эти вещи, в истинность которых никто не верит, прежде казались совершенно не связанными одна с другой.

Замечание немного не в тему, но доказательство теоремы Карпа — Липтона будет поинтереснее целой бочки карпов. Поэтому рассмотрим его прямо сейчас. Предположим, что NP ⊂ P/poly; нужно доказать, что полиномиальная иерархия схлопнется до второго уровня, или, что эквивалентно, что co-NPNP = NPNP. Рассмотрим произвольную задачу в co-NPNP, примерно такую:

Для всех n-битных строк x существует ли n-битная строка y, такая, что Φ (x, y) дает результат «истина»?

(Здесь Φ — некоторая произвольная полиномиального размера булева формула.)

Нам нужно найти вопрос из NPNP, то есть вопрос, в котором квантор существования идет впереди квантора общности, ответ на который совпадает с ответом на приведенный выше вопрос. Но что это может быть за вопрос? Уловка тут вот в чем: сначала мы используем квантор существования, чтобы угадать полиномиального размера строку совета an. Затем мы используем квантор общности, чтобы угадать строку x. Наконец, мы используем строку совета an, — вместе с предположением, что NP ⊂ P/poly, — чтобы самостоятельно угадать y. Таким образом:

Существует ли строка совета an, такая, что для всех n-битных строк x булева формула φ(x, M(x, an)) дает результат «истина»?

Здесь M — это полиномиальная по времени машина Тьюринга, которая при заданном входе x и совете an выдает в качестве результата n-битную строку y, такую, что φ(x, y) дает при вычислении «истину» всякий раз, когда такой y существует. По аналогии с одной из задач предыдущей главы мы можем без труда построить такую M при условии, что умеем решать NP-полные задачи в P/poly.

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

Простая связь заключается в том, что BPP ⊂ P/poly, иными словами, неоднородность по крайней мере столь же мощна, как и случайность. Почему так, как вы считаете?

Ну