Теорема Кука (простым языком)
Я прочитал книгу Garey and Johnson " Компьютеры и непроницаемость - руководство по теории NP- полноты" для курса по алгоритмам; однако, просмотрев материал год спустя, я понял, что никогда не понимал теорему Кука.
Что касается доказательства, я понимаю, почему вначале показано, что SAT сначала находится в NP (первое требование NP-завершения), но я изо всех сил пытаюсь показать, что "другие" NP-полные проблемы в рамках "генетического" полинома преобразовать в SAT.
Мне было интересно, если бы кто-то мог объяснить это более размытым образом, это, возможно, прояснило бы дополнительное прочтение этого раздела.
1 ответ
Доказательство того, что 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. Каждый шаг машины Тьюринга заставляет машину перемещать головку ленты влево или вправо, заменять символ под головкой ленты и перемещать головку ленты влево или вправо.
Прямо перед каждым шагом ТМ мы можем сделать "снимок" состояния машины. Этот снимок будет включать ленту после обрезки бесконечно большого количества заготовок с обеих сторон, положение головки ленты и текущее состояние ТМ. Этот "снимок" более правильно называется мгновенным описанием или идентификатором машины. Вы можете думать об этом как о кортеже (содержимое ленты, состояние, позиция).
Поскольку M - это NTM за полиномиальное время, мы знаем, что он не может выполняться больше, чем p(|w|) шагов при запуске на входной строке w, где p - некоторый полином. Следовательно, при запуске M вычисление будет иметь не более p(|w|) + 1 мгновенных описаний, по одному на каждый шаг. Следовательно, вы можете думать о любом выполнении M как о последовательности этих идентификаторов, записанных один за другим, как (tape0, state0, position0), (tape1, state1, position1), ..., (tapeK, stateK, positionK).
Два порядка в порядке об этих идентификаторах. Во-первых, эти идентификаторы не могут быть абсолютно произвольными. Мы знаем, каким будет первый идентификатор - это будет идентификатор, где лента содержит w, состояние q0, а головка ленты находится над началом строки w. В результате существует только несколько возможных вариантов выбора второго идентификатора на основе каждого недетерминированного выбора, который TM может сделать для своего первого шага. Точно так же число вариантов выбора третьего идентификатора конечно, поскольку этот идентификатор должен быть сформирован, начиная с некоторого допустимого второго идентификатора и применяя одно движение ТМ. В общем, каждый идентификатор должен следовать из законного перемещения ТМ, начиная с предыдущего идентификатора.
Во-вторых, обратите внимание, что если M принимает w, то существует некоторая возможная цепочка идентификаторов, такая, что будет включен последний идентификатор в цепочке, в котором состояние является состоянием принятия машины. И наоборот, если M не принимает w, то никакая возможная цепочка идентификаторов не законно заканчивается тем, что машина находится в состоянии принятия.
Следовательно, сокращение от L до SAT, по сути, создает гигантскую формулу высказываний. Каждая переменная соответствует некоторому фрагменту одного из идентификаторов в цепочке (либо содержимое некоторой определенной ячейки ленты, либо состояние, в котором будет находиться машина, либо положение головки ленты). Затем формула кодирует правила об идентификаторах: первый идентификатор должен быть таким, где машина запускается в состоянии q0, когда головка ленты сканирует первый символ входной строки w, каждый идентификатор должен следовать из предыдущего, и т. Д. В формуле есть последняя часть - машина должна завершиться в состоянии принятия. На самом деле создание всех этих частей формулы довольно сложно (вот почему вы должны взглянуть на учебник). Тем не менее, общий результат состоит в том, что если формула выполнима, есть ряд идентификаторов, которые показывают, что M принимает w (то есть w находится в L(M)), и если это неудовлетворительно, то у M нет способа принять w.
Надеюсь это поможет!