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

…

Последнюю переменную в списке мы назначаем «выходом» схемы. Тогда наша цель в задаче CircuitSAT — решить, существует ли набор x1, …, xn, такой что на выходе схемы получается «истина».

Я утверждаю, что если бы мы могли решить 3-SAT, то мы могли бы решить и задачу CircuitSAT. Почему?

Потому что все, что нам нужно сделать, — это отметить, что каждая реализация CircuitSAT есть на самом деле замаскированная реализация 3-SAT! Всякий раз, когда мы проделываем операции и, или или не, мы соотносим одну новую переменную с одной или двумя старыми. И любое такое соотношение может быть выражено набором предложений, в каждом из которых задействовано не более трех переменных. Так, к примеру,

xn +1:= x 3 или xn

превращается в

xn +1 или не ( x 3)

xn +1 или не ( xn )

не (xn+1) илиx3 илиxn.

Итак, этап 1 пройден. На этапе 2 нужно показать, что если мы можем решить CircuitSAT, то можем решить любую NP-задачу.

Ну хорошо, рассмотрим некоторый пример некоторой NP-задачи. Тогда, по определению NP, существует машина Тьюринга полиномиального времени M, такая, что ответ будет «да» в том и только том случае, когда существует полиномиального размера строка-свидетель w, которую M принимает.

Далее, при наличии этой машины Тьюринга, наша цель — создать схему, которая «имитировала» бы M. Иными словами, мы хотим, чтобы набор входных переменных, при котором схема дает на выходе «истину», существовал в том и только том случае, если существует строка w, которую M принимает.

Как этого добиться? Просто: возьмем и определим весь набор переменных целиком! В нем у нас будет переменная, равная «истине» в том и только том случае, если 37-й бит ленты машины M принимает значение 1 на 42-м шаге по времени. Еще у нас будет переменная, равная «истине» в том и только том случае, если 14-й бит принимает значение 1 на 52-м шаге по времени. А еще у нас будет переменная, которая равна «истине» в том и только том случае, если считывающая головка M будет находиться в 15-м внутреннем состоянии и на 74-й позиции ленты на 33-м шаге по времени. Ну, вы поняли идею.

Затем, записав всю эту кучу переменных, мы записываем также хренову тучу логических соотношений между ними. Если 17-й бит ленты равен 0 на 22-м шаге по времени, а считывающая головка в это время и близко не подходит к 17-му биту, то этот самый 17-й бит и на 23-м шаге по времени останется равным 0. Если считывающая головка на 44-м шаге по времени находится во внутреннем состоянии 5 и считывает на этом шаге 1, а внутреннее состояние 5 по считывании 1 переходит во внутреннее состояние 7, то на 45-м шаге по времени считывающая головка будет находиться во внутреннем состоянии 7. И так далее, и тому