1610906280-c80d8404f2eaa01776b47d41b0f18e85 (824375), страница 25
Текст из файла (страница 25)
Будем говорить, что функция g(n) есть O(f (n)), если существуют натуральныеc > 0 и d > 0 такие, что для всех n ∈ ω имеет место g(n) 6 c·f (n) + d.Предложение 81. Проблема выполнимости булевых формул принадлежит классуNP.Доказательство. Мы приведем неформальное описание недетерминированной машины Тьюринга T , которая по произвольному входному слову w за полиномиальноевремя определяет, является ли w представлением выполнимой булевой формулы илинет.Первая стадия работы машины T состоит в том, что машина проверяет, являетсяли слово w представлением некоторой булевой формулы (если нет, то T сразу выдает отрицательный ответ), и подсчитывает число n пропозициональных переменных,входящих в w.На второй стадии машина T недетерминированным образом «угадывает» набордлины n из нулей и единиц, которые будут рассматриваться в качестве значенийпеременных формулы w. Другими словами, на данном этапе вычисление разветвляется на 2n параллельных ветвей, каждая из которых соответствует одному наборузначений переменных.На третьей стадии угаданные значения (вдоль каждой ветви вычислений) подставляются вместо соответствующих вхождений переменных в слово w.
Чтобы закрыть дыры, образующиеся в слове w в результате подстановки одного символа 0или 1 вместо десятичного представления пропозициональной переменной, потребуется сделать сдвиги символов на ленте машины. Далее вычисляется значение формулыпри данном наборе значений переменных.Если хотя бы на одной ветви вычислений значение формулы равно 1, то машинавыдает положительный ответ. Если на всех ветвях значения нулевые, то машинавыдает отрицательный ответ. В целом, все три стадии работы машины T требуютO(|w|2 ) шагов.§ 27. Теорема Кука101Теорема 82 (С.
Кук, 1971). Проблема выполнимости булевых формул NP-полна.Доказательство. Выше мы уже показали, что проблема выполнимости лежит вклассе NP. Осталось доказать, что любой язык L из класса NP полиномиально сводится к проблеме выполнимости булевых формул. Пусть T — недетерминированнаямашина Тьюринга, распознающая L за полиномиальное время. Мы опишем алгоритм, который по произвольному слову w, поданному на вход машины T , строит заполиномиальное время булеву формулу Φ такую, что Φ выполнима тогда и только тогда, когда T распознает w. Полином, который ограничивает время построенияформулы Φ по слову w, будет зависеть от T .Пусть q0 , q1 , . .
. , qs — внутренние состояния машины T , a0 , a1 , . . . , am — символывнешнего алфавита T , а полином p(n) — временна́я сложность машины T . Предположим, что слово w, поданное на вход машины T , имеет длину n. Согласно определению, T распознает w тогда и только тогда, когда существует конечная последовательность конфигурацийM0 `T M1 `T . . . `T Mq ,такая, что M0 = q1 a0 wa0 , Mq = uq0 a1 v для некоторых слов u, v; в данном вычислениине достраиваются новые ячейки слева; q 6 p(n); и ни одна из указанных конфигураций не занимает более чем p(n) ячеек на ленте.Построим булеву формулу Φ, моделирующую последовательность конфигураций,проходимых машиной T . Каждый набор значений переменных формулы Φ будет соответствовать, самое большее, одной последовательности конфигураций, возможно,некорректной (т.
е. такой, которая не может на самом деле реализоваться). ФормулаΦ будет принимать значение 1 тогда и только тогда, когда данный набор значений переменных будет соответствовать последовательности конфигураций M0 , M1 , . . . , Mq ,приводящей к распознаванию входа. В качестве пропозициональных переменныхформулы Φ будем использовать следующие переменные (мы также указываем ихподразумеваемую интерпретацию):а) переменная Xhi, j, ti принимает значение 1 тогда и только тогда, когда i-аяячейка в текущей конфигурации машины T содержит символ aj в момент времени t. Здесь 1 6 i 6 p(n), 0 6 j 6 m, 0 6 t 6 p(n);б) переменная Y hk, ti принимает значение 1 тогда и только тогда, когда машинаT в момент времени t находится в состоянии qk .
Здесь 0 6 k 6 s, 0 6 t 6 p(n);в) переменная Zhi, ti принимает значение 1 тогда и только тогда, когда головкамашины в момент времени t обозревает i-ую ячейку текущей конфигурации.Здесь 1 6 i 6 p(n), 0 6 t 6 p(n).Таким образом, пропозициональных переменных всего O(p2 (n)), и их десятичныепредставления в записи формулы Φ будут содержать не более c log10 n разрядов, гдеc — константа, зависящая от полинома p. В дальнейшем удобно представлять себекаждую пропозициональную переменную как один символ, а не как слово из c log10 nсимволов. Эта потеря множителя c log10 n никак не отразится на полиномиальнойограниченности времени, затрачиваемого на вычисление той или иной функции.Для построения формулы Φ нам потребуется вспомогательная булева формулаU (P1 , . . .
, Pr ), которая принимает значение 1 тогда и только тогда, когда в точности102Глава V. Теория сложности алгоритмоводин из ее аргументов P1 , . . . , Pr принимает значение 1. Данную формулу можновыразить следующим образом:³´U (P1 , . . . , Pr ) = (P1 ∨ . . . ∨ Pr ) & & (¬Pi ∨ ¬Pj ) .i6=jФормальная запись формулы U (P1 , . . .
, Pr ) имеет длину O(r2 ) (напомним, что мысчитаем переменную одним символом).Не ограничивая общности, будем считать, что машина T модифицирована так,что на входе w она делает ровно p(n) шагов, и все конфигурации, проходимые машиной, содержат ровно p(n) ячеек. Этого можно добиться, дополнив все конфигурациинужным количеством фиктивных ячеек и заставив T , если нужно, работать послеостановки, но не изменяя заключительной конфигурации и не сдвигая головки.
Поэтому будем строить Φ как конъюнкцию семи формул A, B, C, D, E, F, G, которыеутверждают, что на входе w машина T находилась последовательно в конфигурациях M0 , . . . , Mq , причем каждое Mi имеет длину p(n), q = p(n), и в результате работымашина T распознала слово w. Данное утверждение равносильно совокупности следующих условий:1) В каждой конфигурации головка обозревает ровно одну ячейку.2) В каждой конфигурации в каждой ячейке ленты стоит ровно один символ.3) Каждая конфигурация содержит ровно одно состояние.4) При переходе от одной конфигурации к следующей может измениться содержимое только одной ячейки.5) Изменение состояния, положения головки и содержимого ячейки при переходе от одной конфигурации к другой происходит в соответствии с программоймашины T .6) Первая конфигурация имеет вид q1 a0 wa0 .7) Последняя конфигурация имеет вид uq0 a1 v для некоторых слов u, v.Перейдем к непосредственному построению формул A, B, C, D, E, F, G, которыесоответствуют условиям (1)–(7).1) A утверждает, что в каждый момент времени машина T обозревает ровно однуячейку.
Введем формулуAt = U (Zh1, ti, Zh2, ti, . . . , Zhp(n), ti),которая утверждает, что в момент t обозревается в точности одна ячейка. ТогдаA = A0 &A1 & . . . &Ap(n) . Заметим, что формула A имеет длину O(p3 (n)) и ееможно записать за такое же время.2) B утверждает, что каждая ячейка ленты в каждый момент времени содержитровно один символ. Введем формулуBit = U (Xhi, 0, ti, Xhi, 1, ti, . . . , Xhi, m, ti),§ 27. Теорема Кука103которая утверждает, что i-ая ячейка ленты в момент времени t содержит ровноодин символ.
Тогда B = &Bit . Длина каждой формулы Bit не зависит от n,i,tпоскольку величина m зависит только от машины T . Следовательно, формулаB имеет длину O(p2 (n)).3) C утверждает, что в каждый момент времени t машина T находится в одном итолько одном состоянии, т. е.C=&U (Y h0, ti, Y h1, ti, . . . , Y hs, ti).06t6p(n)Так как число s зависит только от машины T , то C имеет длину O(p(n)).4) D утверждает, что в любой момент времени t может измениться содержимоене более, чем одной ячейки, т.
е.³´D = & Zhi, ti ∨ (Xhi, j, ti&Xhi, j, t + 1i) ∨ (¬Xhi, j, ti&¬Xhi, j, t + 1i) .i,j,tФормула Zhi, ti∨(Xhi, j, ti&Xhi, j, t+1i)∨(¬Xhi, j, ti&¬Xhi, j, t+1i) утверждает,что либоа) в момент t головка обозревает i-ую ячейку, либоб) символ aj записан в i-ой ячейке в момент t + 1 тогда и только тогда, когдаон был записан там в момент t.Поскольку A и B утверждают, что в момент t головка обозревает только однуячейку и i-ая ячейка содержит лишь один символ, то в момент времени t либо головка обозревает i-ую клетку, либо содержимое i-ой клетки не меняется.Длина формулы D равна O(p2 (n)).5) E утверждает, что очередная конфигурация машины T получается из предыдущей с помощью применения одной команды из программы машины T . ПустьEijkt означает одно из следующих утверждений:а) в момент t i-ая ячейка не содержит символ aj ,б) в момент t головка не обозревает i-ую ячейку,в) в момент t машина не находится в состоянии qk ,г) при переходе от момента t к моменту t + 1 новая конфигурация машины получается из предыдущей с помощью применения одной команды изпрограммы машины T .Пусть для данных значений k и j списком{qk aj → qk1 aj1 S1 , qk aj → qk2 aj2 S2 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
