Доказательство того, что SAT является NP-трудным (то есть, что существует полиномиальное время редукции от каждой NP-задачи к SAT), нетривиально. Я попытаюсь дать интуитивное представление о том, как это работает, но я не собираюсь вдаваться во все детали. Для этого вы, вероятно, захотите обратиться к учебнику.
Начнем с любого NP-языка L. По определению, тот факт, что L является NP-языком, означает, что для языка L существует недетерминированная машина Тьюринга с полиномиальным временем. Это означает, что машина M принимает строку w, если и только если w принадлежит L, и, кроме того, время выполнения M есть некоторый полином p(n). Сокращение от L к SAT будет работать, показывая, что вы можете построить пропозициональную формулу, которая по существу имитирует действие M на некоторой конкретной строке w. Эта формула обладает тем свойством, что M принимает w (то есть w принадлежит L) тогда и только тогда, когда результирующая пропозициональная формула выполнима.
Не совсем понятно, что это вообще возможно. Чтобы увидеть, как это работает, мы воспользуемся стандартной техникой сведения задач, связанных с НП, друг к другу. Подумайте об операции M над строкой w. Поскольку M — машина Тьюринга, когда мы запускаем M с w, она начинается с w, записанного на ленте (окруженного бесконечным числом пробелов), в некотором состоянии q0, и с ленты над первый символ w. Каждый шаг машины Тьюринга заставляет машину перемещать головку ленты влево или вправо, заменять символ под головкой ленты и перемещать головку ленты влево или вправо.
Прямо перед каждым шагом ТМ мы можем сделать «моментальный снимок» состояния машины. Этот снимок будет включать в себя ленту после обрезки бесконечного множества пробелов с обеих сторон, положение головки ленты и текущее состояние TM. Этот «моментальный снимок» правильнее называть мгновенным описанием или идентификатором машины. Вы можете думать об этом как о кортеже (содержимое ленты, состояние, позиция).
Поскольку M — NTM с полиномиальным временем, мы знаем, что он не может выполняться более чем за p(|w|) шагов при работе с входной строкой w, где p — некоторый полином. Следовательно, при выполнении M вычисление будет иметь не более p(|w|) + 1 мгновенного описания, по одному на каждый шаг. Следовательно, вы можете думать о любом выполнении M как о серии этих идентификаторов, записанных один за другим, как (лента0, состояние0, позиция0), (лента1, состояние1, позиция1), ..., (лентаK, состояниеK, положение К).
Два замечания по поводу этих идентификаторов. Во-первых, эти идентификаторы не могут быть абсолютно произвольными. Мы знаем, каким будет первый идентификатор — это будет идентификатор, в котором лента содержит w, состояние — q0, а головка ленты находится над началом строки w. В результате есть только несколько возможных вариантов того, каким будет второй идентификатор, основанный на каждом из недетерминированных вариантов, которые ТМ может сделать для своего первого шага. Точно так же количество вариантов для третьего идентификатора конечно, поскольку этот идентификатор должен быть сформирован, начиная с некоторого допустимого второго идентификатора и применяя один ход TM. В более общем случае каждый идентификатор должен следовать из допустимого перемещения TM, начиная с предыдущего идентификатора.
Во-вторых, обратите внимание, что если M принимает w, то существует некоторая возможная цепочка идентификаторов, такая, что последний идентификатор в цепочке будет включен, в котором состояние является принимающим состоянием машины. И наоборот, если M не принимает w, то никакая возможная цепочка идентификаторов не будет законно заканчиваться машиной в принимающем состоянии.
Таким образом, редукция от L к SAT работает, по существу, за счет построения гигантской пропозициональной формулы. Каждая переменная соответствует какой-то части одного из идентификаторов в цепочке (либо содержимому какой-то конкретной ячейки ленты, либо в каком состоянии будет машина, либо где будет головка ленты). Затем формула кодирует правила, касающиеся идентификаторов: первый идентификатор должен быть таким, при котором машина запускается в состоянии q0, когда головка ленты сканирует первый символ входной строки w, каждый идентификатор должен следовать из предыдущего и т. д. Осталась последняя часть формулы — машина должна закончиться в принимающем состоянии. На самом деле построить все эти части формулы довольно сложно (поэтому вам следует заглянуть в учебник). Однако конечным результатом является то, что если формула выполнима, то имеется ряд идентификаторов, которые показывают, что M принимает w (поэтому w находится в L(M)), а если это невыполнимо, то M никак не может принять w.
Надеюсь это поможет!
person
templatetypedef
schedule
02.10.2014
