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

не ( x 2) или x 4

не ( x 4) или не ( x 5) или x 6

…

Вопрос в том, существует ли какой-нибудь способ задать переменным x1, …, xn значения «истина» или «ложь» так, чтобы все предложения формулы оказались выполнены (то есть значение каждого из них было «истина»).

Очевидно, что задача 3-SAT относится к классу NP. Почему? Верно: потому что если кто-то даст вам работающий комплект x1, …, xn, то проверить факт его пригодности несложно!

Наша цель — доказать, что 3-SAT является NP-полной. Что для этого требуется? Ну, необходимо показать, что, если у нас есть оракул для 3-SAT, мы можем с его помощью решить не только 3-SAT за полиномиальное время, но и вообще любую NP-задачу. Кажется, очень непросто! Однако чуть позже, задним числом, вы увидите, что делается это почти тривиально.

Доказательство складывается из двух этапов. Этап 1 — показать, что если бы мы могли решить 3-SAT, то мы могли бы решить и более «общую» задачу выполнимости для булевой схемы (CircuitSAT). Этап 2 — показать, что, имея возможность решить CircuitSAT, мы могли бы решить любую NP задачу.

В CircuitSAT нам задается булева схема и… погодите-ка. Инженеры, слушайте внимательно: в информатике в «схеме» никогда не бывает ни контуров, ни циклов! В ней также нет резисторов и диодов и вообще никаких таких странных вещей. Для нас схема — это просто объект, где для начала у вас есть n булевых переменных x1, …, xn, а затем вы можете сколь угодно долго определять новые переменные, которые получаются из уже определенных посредством операций и, или и не. Примерно так:

xn +1:= x 3 или xn

xn +2:= не ( xn +1)

xn +3:=