Доказательство того, что SAT NP-жесткий (то есть сокращение от полиномиального времени от каждой проблемы NP до SAT), является нетривиальным. Я попытаюсь дать интуицию, как это работает, но я не собираюсь перебирать все детали. Для этого вы, вероятно, захотите ознакомиться с учебником.
Начнем с использования любого языка NP. По определению факт, что L является NP-языком, означает, что для языка L. существует недетерминированная полиномиальная машина Тьюринга M. Это означает, что машина M принимает строка w тогда и только тогда, когда w принадлежит L, а поверх этого время выполнения M - некоторый многочлен p (n). Сокращение от L до SAT будет работать, показывая, что вы можете построить пропозициональную формулу, которая по существу имитирует работу M на некоторой конкретной строке w. Эта формула обладает тем свойством, что M принимает w (т. Е. W принадлежит L) тогда и только тогда, когда результирующая пропозициональная формула является выполнимой.
Не совсем ясно, что это можно сделать вообще. Чтобы увидеть, как это работает, мы будем использовать стандартный метод для сокращения проблем, связанных с ТМ друг с другом. Подумайте о работе M на строке w. Так как M является машиной Тьюринга, когда мы запускаем M с w, то начинается с w, записанного на ленте (в окружении бесконечно большого числа пробелов), в некотором состоянии q и с лентой над первым символом w , Каждый шаг машины Тьюринга заставляет машину перемещать ленту влево или вправо, чтобы заменить символ под лентой, и переместить ленту влево или вправо.
Перед каждым шагом ТМ мы можем взять «моментальный снимок» состояния машины. Этот снимок будет включать в себя ленту после обрезки бесконечного количества заготовок с обеих сторон, положения головки ленты и текущего состояния ТМ. Этот «снимок» более правильно называется мгновенным описанием или ID машины. Вы можете рассматривать его как кортеж (содержимое ленты, состояние, положение).
Поскольку M является NTM с полиномиальным временем, мы знаем, что он не может работать более чем на p (| w |) шагах при запуске на входной строке w, где p - некоторый многочлен. Поэтому, когда M работает, вычисление будет иметь не более p (| w |) + 1 мгновенных описаний, по одному для каждого шага. Следовательно, вы можете думать о любом выполнении M как серии этих идентификаторов, выписанных один за другим, как (tape0, state0, position0), (tape1, state1, position1), ..., (tapeK, stateK, positionK).
В отношении этих идентификаторов имеются два наблюдения. Во-первых, эти идентификаторы не могут быть полностью произвольными. Мы знаем, каким будет первый идентификатор - он будет идентификатором, где лента удерживает w, состояние равно q , а ленточная головка находится над началом строки w. В результате существует лишь несколько возможных вариантов выбора второго идентификатора, основанного на каждом из недетерминированных вариантов, которые ТМ может сделать для своего первого шага.Аналогично, количество вариантов для третьего идентификатора является конечным, так как этот идентификатор должен быть сформирован, начиная с некоторого юридического второго идентификатора и применяя один шаг ТМ. В более общем плане, каждый идентификатор должен следовать из юридического движения TM, начинающегося с предыдущего идентификатора.
Во-вторых, обратите внимание, что если M принимает w, то существует некоторая возможная цепочка идентификаторов, так что последний идентификатор в цепочке будет включен, в котором состояние является принимающим условием машины. И наоборот, если M не принимает w, то никакая возможная цепочка идентификаторов юридически не заканчивается машиной в состоянии принятия.
Таким образом, сокращение от L до SAT ведет, по существу, к созданию гигантской формулы пропозиции. Каждая переменная соответствует некоторой части одного из идентификаторов в цепочке (либо содержимое определенной ячейки ленты, либо то, в каком состоянии находится устройство, или где будет лента). Затем формула кодирует правила об идентификаторах: первый идентификатор должен быть таким, где машина запускает состояние q с лентой, на которой сканируется первый символ входной строки w, каждый идентификатор должен следовать из предыдущего и т. д. Есть одна последняя часть формулы - машина должна заканчиваться в принимающем состоянии. На самом деле собрать все эти части формулы довольно сложно (вот почему вы должны смотреть на учебник). Однако чистый результат состоит в том, что если формула является выполнимой, существует серия идентификаторов, которые показывают, что M принимает w (так что w находится в L (M)), и если это неудовлетворительно, тогда нет возможности для M принять w.
Надеюсь, это поможет!
Это похоже на лучшую подгонку [CS Exchange] (http://cs.stackexchange.com/). Однако * очень * короткое описание: если проблема NP, тогда она разрешима в поли-время некоторой нестандартной машиной Тьюринга. Далее следует аргумент, что мы можем имитировать упомянутую машину Тьюринга по проблеме SAT, путем кодирования конечного автомата и памяти в логике. Затем вы продолжаете доказывать, что полученная длина формул является полиномиальной по характеристикам машины Тьюринга и, следовательно, - во входной длине. – Ordous