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

к нему множество задач, где вас можно убедить в ответе «да» посредством взаимодействия с доказателем. Прежде мы говорили о таких классах, как MA и AM, где вы имеете постоянное число актов взаимодействия. В классе MA доказатель высылает вам сообщение, а вы проводите вероятностный расчет, чтобы его проверить. В классе AM вы посылаете доказателю сообщение, затем доказатель высылает вам ответное сообщение, а вы проводите вероятностный расчет. Выясняется, что с любым постоянным числом актов взаимодействия вы получаете один и тот же класс AM, так что не будем мелочиться и разрешим полиномиальное число взаимодействий. В результате получим класс IP. Что сделали Фортноу и Сипсер? Они привели способ построения оракула, относительно которого co-NP ⊄ IP. Они показали, что относительно этого оракула невозможно подтвердить невыполнимость формулы посредством полиномиального числа актов взаимодействия с доказателем. В соответствии со стандартной парадигмой данной области информатики мы, разумеется, не можем доказать безусловно, что co-NP ⊄ IP, но это все же дает нам кое-какие свидетельства; это указывает нам, истинность чего нам следует ожидать.

А теперь настоящая бомба (открыли ее Лунд, Фортноу, Карлофф и Нисан, отсюда название — «теорема LFKN»)[132]. Как показать в «реальном», нерелятивизированном мире невыполнимость формулы? Скорее всего, нам придется каким-то образом использовать структуру этой формулы. Придется воспользоваться тем, что это булева формула, заданная нам явно, а не абстрактная булева функция. Что мы сделаем? Будем считать, что это задача 3-SAT. Поскольку задача 3-SAT относится к NP-полным, это предположение не приведет к потере общности. У нас имеется некоторое количество условий (n штук), в каждом из которых задействовано по три переменных, и мы хотим удостовериться, что не существует способа удовлетворить всем условиям.

Что мы делаем? Отображаем нашу формулу на многочлен над конечным полем. Этот фокус называется арифметизацией. По существу, мы собираемся преобразовать данную логическую задачу в алгебраическую, что расширит наши возможности по работе с ней. Вот как это работает: мы записываем нашу реализацию 3-SAT в виде произведения многочленов третьей степени. Каждое условие — то есть каждое «или» трех литералов — просто превращается в 1 минус произведение 1 минус каждый из литералов: к примеру, (x или y или z) превращается в

1 — (1 — x ) (1 — y ) (1 — z ).

Обратите внимание: в случае, когда x, y и z могут принимать только значения 0 и 1, соответствующие значениям ложь и истина, этот многочлен в точности эквивалентен логическому выражению, с которого мы начали. Но теперь мы можем заново интерпретировать этот многочлен и сказать, что он определен над некоторым гораздо более обширным полем. Выберем некоторое достаточно большое простое число N, и мы скажем, что наш многочлен определен над GFN (полем из N элементов). Я обозначу этот многочлен P(x1, …, xn).

Если формула невыполнима, то какую бы подстановку x1, …, xn мы ни выбрали для переменных, в формуле непременно встретится какое-то условие, которое не будет выполнено. Следовательно, один из многочленов третьей степени, которые мы перемножаем, примет значение 0, а значит, и произведение будет равно нулю. Таким образом, отсутствие удовлетворительных назначений эквивалентно получению нуля при суммировании P(x1, …, xn) по всем 2n возможным булевым подстановкам x1, …, xn.

Проблема, разумеется, в том, что результат не кажется сколько-нибудь проще, чем то, с чего мы начинали! Мы получили сумму экспоненциального числа слагаемых, и нам необходимо проверить каждое из них и убедиться в том, что все они равны нулю. Но здесь мы можем воспользоваться помощью доказателя. Если у нас просто имеется строка нулей и он просто сообщает нам, что на всех позициях в ней нули, то мы ему не поверим. Но теперь мы перенесли все на более обширное поле, и у нас появилась некоторая структура, с которой можно работать.

Итак, что мы теперь можем сделать? Мы просим доказателя просуммировать для нас по всем 2n–1 возможным подстановкам переменных x2, …, xn, не фиксируя x1. Таким образом, доказатель посылает нам одномерный многочлен Q1 первой переменной. Поскольку многочлен, с которого мы начали, имел степень poly (n), доказатель может сделать это, прислав нам полиномиальное число коэффициентов. Он может прислать нам этот одномерный полином. Теперь мы должны убедиться в том, что Q1(0) + Q1(1) = 0 (все по модулю N). Как это сделать? Доказатель дал нам предполагаемое значение всего многочлена. Так что мы просто выбираем случайным образом r1 из нашего поля. Далее нам бы хотелось убедиться в том, что Q1(r1) действительно равняется тому, чему должно равняться. Забудьте про 0 и 1, мы просто идем куда-то в другое место нашего поля. Далее, мы посылаем r1 доказателю. В ответ доказатель посылает нам новый многочлен Q2, в котором первая переменная фиксирована и равна r1, вторая (x2) не фиксирована, а x3, …, xn просуммированы по всем возможным булевым значениям (как раньше). Мы по-прежнему не знаем точно, что доказатель нам не лжет и не высылает бессмысленных многочленов. Что же мы можем сделать?

Проверяем, что Q2(0) + Q2(1) = Q1(r1), затем выбираем случайным образом другой элемент r2 и вновь пересылаем его доказателю. В ответ он