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

на квантовом компьютере NP-полные задачи. Очень часто такие люди чрезвычайно уверены в своем «знании».

Прежде чем мы станем разбираться в возможной NP-полноте разложения на простые множители, позвольте мне по крайней мере объяснить, почему я считаю, что задача разложения не относится к классу P. Могу ли я сказать, что никто не может эффективно решить ее на практике? Хотя это не слишком хороший аргумент, все, безусловно, рассчитывают, что эта задача не относится к P. Следует признать, что у нас нет столь же серьезных причин считать, что факторизация не относится к P, какие есть считать, что P ≠ NP. Мнение о том, что факторизация, может быть, все же относится к P и мы просто недостаточно знаем о теории чисел, чтобы доказать это, можно даже счесть почти респектабельным. Если вы потратите две секунды, чтобы обдумать это, то поймете, что задача разложения на простые множители имеет глубокие отличия от известных NP-полных задач. Если я дам вам булеву формулу, то у нее может вообще не оказаться удовлетворяющих всем условиям входных данных, дающих на выходе истину, может оказаться один набор таких данных, а может оказаться их 10 триллионов. Вы просто не можете знать этого заранее. Но если я дам вам 5000-значное целое число, то вы, вероятно, не сможете сразу сказать, на какие множители оно раскладывается, но будете точно знать, что оно имеет одно и только одно разложение. (Насколько я помню, парень по имени Евклид доказал это довольно давно.) Уже это говорит нам, что разложение на простые множители — в чем-то «особая» задача: в отличие от того, что нам вроде бы известно о NP-полных задачах, факторизация обладает некоей структурой, которую алгоритмы могут попытаться использовать. И алгоритмы действительно ее используют: нам известен классический алгоритм под названием «решето числового поля», позволяющий разложить n-значное целое число на множители примерно за

шагов, а не за ~2n/2 шагов, которые потребовались бы для перебора всех возможных делителей. (Кстати, а почему только ~2n/2 шагов, а не ~2n?) И, разумеется, нам известен алгоритм Шора, позволяющий разложить n-битное целое число за ~ n² шагов на квантовом компьютере, то есть за квантовое полиномиальное время. Вопреки популярному мнению, мы не знаем квантового алгоритма, позволяющего решать NP-полные задачи за полиномиальное время. Если бы такой алгоритм существовал, то он наверняка резко отличался бы от алгоритма Шора.

Но можем ли мы указать конкретно, чем именно разложение на простые множители отличается от известных NP-полных задач в терминах теории вычислительной сложности? Да, можем. Во-первых, чтобы превратить разложение на множители в проблему разрешимости (да-или-нет), нам придется задавать примерно такие вопросы: если дано положительное целое число N, то имеет ли N простой множитель с последней цифрой 7? Я утверждаю, что эта задача относится не просто к NP, но к NP ∩ co-NP. Почему? Ну, предположим, кто-то дал вам вариант разложения N на простые множители. Разложение существует только одно. Поэтому если в нем имеется простой множитель с последней цифрой 7, это можно проверить, и если такого множителя нет, это можно проверить тоже.

Вы можете сказать: «Но откуда мне знать, что мне на самом деле дали разложение на простые множители? Конечно, если кто-то дает мне набор чисел, я могу убедиться в том, что при перемножении они дают N, но откуда мне знать, что все они простые?» Для этого вам придется принять на веру кое-что, о чем я уже говорил: что если вы хотите просто проверить, простое это число или составное, а не найти сами сомножители, то сделать это можно за полиномиальное время. О'кей, если вы с этим согласны, то задача разложения на простые множители относится к классу NP ∩ co-NP.

Из этого мы можем заключить, что если разложение на множители — NP-полная задача, то NP должен равняться co-NP. (Почему?) А поскольку мы не верим, что NP = co-NP, то можно считать это сильным доводом (хотя и не доказательством) в пользу того, что, несмотря на всех тех людей, о которых я вам рассказывал, факторизация не является NP-полной задачей. Если мы это принимаем, остается только два варианта: факторизация либо относится к классу P, либо является одной из тех «промежуточных» задач, чье существование гарантируется теоремой Ладнера. Большинство специалистов склоняется ко второму варианту, хотя и с меньшей уверенностью, чем наша уверенность в том, что P ≠ NP.

На самом деле может оказаться даже, что P = NP ∩ co-NP, но при этом все равно P ≠ NP. (Такой вариант подразумевал бы, что NP ≠ co-NP.) Так что если вам кажется слишком простым доказательство обоих утверждений — и P ≠ NP, и NP ≠ co-NP, то вашей следующей целью может стать доказательство утверждения P ≠ NP ∩ co-NP!

Если P, NP и co-NP недостаточно, чтобы поколебать ваш мир, вы можете обобщить эти классы в гигантскую кучу, которую мы, специалисты по теоретической информатике, называем полиномиальной иерархией.

Обратите внимание, что вы можете представить любую реализацию NP-задачи в форме:

Существует ли n-битная строка X, такая, что A (X) = 1?

Здесь A — функция, вычислимая за полиномиальное время.

Аналогично вы можете представить любую задачу co-NP в форме:

Верно ли A (X) = 1 для любого X?

Но что произойдет, если добавить к этому еще один квантор, примерно так:

Существует ли X, такой, что A (X, Y) = 1 для любого Y?

Для любого X существует ли Y, такой, что A (X, Y) = 1?

Такие задачи приводят нас к двум новым классам сложности, которые называются Σ2P и Π2P соответственно. Π2P — это «дополнение» к Σ2P в том же смысле, в каком co-NP есть дополнение к NP. Кроме того, мы можем добавить и третий квантор:

Существует ли X, такой, что для любого Y существует Z, такой, что A (X, Y, Z) = 1?

Для любого X существует ли Y, такой, что для любого Z имеем A (X, Y, Z) = 1?

Это дает нам классы сложности Σ3P и Π3P соответственно. Должно быть очевидно, как обобщить это до ΣkP и ΠkP для любого большего k. (На полях отмечу, что когда k = 1 мы получаем Σ1P = NP и Π1P = co-NP. Почему?) Затем, взяв