А.А. Сапоженко - Некоторые вопросы сложности алгоритмов (1158759), страница 5
Текст из файла (страница 5)
Формулы C и D строятся аналогично B.Формула E утверждает, что выполнены начальные условия.i1i2in11E = Q11 &S1,1 &P1,1&P2,1&...&Pn,1&Pn+1,1&...&PT,1,где w = ai1 ai2 ...ain — входное слово, q1 — начальное состояние и a1 — пустой символ.Формула F утверждает, что для каждого t преобразование слова на ленте, сдвиг головки и изменение состояния осуществляются в соответствии с программой НМТ. Если же ячейка не обозревается, то содержимое ее не изменяется.
Fпредставляет собой конъюнкцию формул Fs,t по всем s, t. Формула Fs,t утверждает:1) если ячейка с номером s не обозревается на шаге t, то символ, находящийся в ней, не изменяется;132) если же s-я ячейка обозревается на шаге t, то изменения состояния и символа в обозреваемой ячейке, а также сдвигголовки производятся в соответствии с программой НМТ по символу, находящемуся в s-й ячейке и состоянию НМТ.Пусть Rs,t,i,j означает следующее: при условии, что на шаге t обозревается ячейка s, из того, что в обозреваемой ячейкеленты записан символ ai и НМТ находится в состоянии qj , следует, что НМТ действует в соответствии хотя бы с однойиз команд, начинающихся с пары ai qj . Пусть, например, в программе НМТ присутствуют две команды с началом ai , qj :ai qj → ai1 qj1 L и ai qj → ai2 qj2 R.
Тогда высказывание Rs,t,i,j имеет следующий вид:j1j2i2i ∨ Qj ∨ P i1Rs,t,i,j = Ps,tts,t+1 &Qt+1 &Ss−1,t+1 ∨ Ps,t+1 &Qt+1 &Ss+1,t+1 .Высказывание Fs,t имеет видFs,t = S s,t &V1≤i≤li(Ps,t__iPs,t+1)Ss,t &WW1≤i≤l 1≤j≤rRs,t,i,j .Заметим, что формулы для Rs,t,i,j и Fs,t не являются КНФ. Однако каждую из них можно представить, например, совершенной КНФ. Важным является то, что при фиксированных s и t число переменных, от которых зависят эти формулы,ограничено константой, зависящей только от l и r. Поэтому после перехода к КНФ получатся формулы, длина которыхтакже ограничена некоторой константой, зависящей только от l и r.Наконец, формула G утверждает, что на некотором шаге НМТ придет в принимающее заключительное состояние. Пустьтаковым является qr .
Имеем__ _G = Qr1 Qr2 ... QrT .Нетрудно проверить, что построенная таким образом формула A обладает всеми требуемыми свойствами.Список литературы[1] Кибернетический сборник (Нов. серия), No 12 , М.: МИР, 1975, С. 5–10.[2] А. Ахо, Д. Хопкрофт, Д. Ульман// Построение и анализ вычислительных алгоритмов, М.: Мир, 1979, 536 С.[3] М.Гэри, Д.Джонсон, Вычислительные машины и труднорешаемые задачи, М.: МИР, 1982, 416 С.[4] J. Edmonds, Paths, trees and flowers,// Canad. J.
Math., VIII, 1965, С. 449-467.[5] С. В. Яблонский “Введение в дискретную математику"М.: Наука, 1986, 384 C.1425О задачах выполнимости КНФПараграф посвящен некоторым разновидностям задач о выполнимости КНФ. Определим k-КНФ как конъюнкцию скобок,каждая из которых является дизъюнкцией не более k букв, каждая из которых является переменной или ее отрицанием.Задача k-ВЫП состоит в распознавании выполнимости произвольной k-КНФ.
Здесь доказывается принадлежность задачиВЫП классу NP, полиномиальность задачи 2-ВЫП и N P -полнота задачи 3-ВЫП.Пусть КНФ K зависит от переменных x1 , ..., xn (не обязательно существенно). Кодом КНФ K является слово W (K)в алфавите {0, 1, &, ∨, (, )}, полученное заменой в K каждой буквы xσi двоичным словом вида σα1 . . . αm , где α1 . .
. αmявляется двоичным разложением числа i, причем m = dlog2 ne.Теорема 5.1 Задача ВЫП принадлежит классу NPДоказательство. Требуется доказать существование недетерминированной машины Тьюринга (сокращенно НМТ), распознающей язык ВЫП. Определение НМТ дано выше (см. параграф 4). Содержательно говоря, алгоритм распознаваниявыполнимости КНФ K состоит в следующем.
Имея на входе КНФ K, НМТ M строит две КНФ K0 и K1 , получающиеся изK путем подстановки вместо переменной x1 соответственно констант 0 и 1. Затем НМТ M повторяет процедуру подстановкиконстант 0 и 1 вместо переменной x2 и т.д. Всякий раз НМТ M прослеживает процесс подстановки параллельно (см. рис.5.1).Рис. 5.1В результате после осуществления n подстановок всякий раз будет получена некоторая КНФ с константами вместопеременных.
Проверка равенства каждой из таких КНФ единице, очевидно, может быть осуществлена детерминированноймашиной Тьюринга (а, значит, и НМТ) за время (число шагов), не превосходящее O(L), где L длина кода W (K). Еслисоответствующая КНФ равна единице, НМТ останавливается в принимающем состоянии, если КНФ равна нулю, то — вотвергающем. КНФ K выполнима, если хотя бы при одной подстановке констант НМТ останавливается в принимающемсостоянии.Нетрудно составить программу НМТ, которая, имея на входе код W (K) КНФ K, реализует описанные выше преобразования.
НМТ будет иметь счетчик индексов переменных для того, чтобы знать, вместо какой переменной в данный моментподставляются константы. Выработать код индекса переменной на очередном шаге можно, прибавив 1 к двоичному счетчикуиндексов. Для этого требуется не более O(m) = O(log2 n) шагов.Подстановку константы вместо буквы xσi можно представлять себе как подстановку специальных символов 0∗ и 1∗ вместо первой координаты кода буквы xσi . При этом мы полагаем, что символы 0∗ и 1∗ входят в алфавит НМТ и отличны отсимволов 0 и 1, используемых для кодирования индексов переменных.
Осуществляя преобразования, связанные с подстановкой констант вместо переменной xi , НМТ сначала делает выбор, какую из констант подставлять (недетерминированнаячасть i-го этапа), а затем подстановка осуществляется детерминированным алгоритмом. Именно, следует отыскать в словекод очередной буквы вида xσi и заменить его первый разряд одним из двух символов 0∗ и 1∗ . Для распознавания того, чтозаданное подслово длины m = dlog2 ne слова W длины L совпадает с двоичной записью числа i, хранящейся на ленте, скажем, непосредственно перед самим словом, достаточно O(mL) шагов.
Число таких замен не превосходит L. Таким образом,при заданном коде индекса переменной замену последней на константу можно осуществить не более чем за O(L2 log2 n)шагов. Ясно, что число шагов в каждом вычислении не превосходит O(nL2 log2 n) = O(L3 ), где L длина входа. За этовремя НМТ придет в некоторое заключительное состояние. Если среди заключительных состояний окажется хотя бы однопринимающее, то КНФ K выполнима. В противном случае она не является выполнимой. Таким образом, построенная НМТраспознает язык ВЫП за время O(L3 ).215Следствие 5.1 Задача ВЫП является N P -полной.Утверждение следует из теоремы Кука и теоремы 5.1.Определим задачу k-ВЫП ее входом и свойством.ВХОД: 3-КНФ F (x1 , .
. . , xn ).СВОЙСТВО: выполнимость.Теорема 5.2 2-ВЫП ∈ P.Доказательство. Мы представим полиномиальный алгоритм распознавания 2-выполнимости. Идея алгоритма состоитв переходе от КНФ K, выполнимость которой требуется установить, к новой КНФ K 0 , выполнимой тогда и только тогда,когда K выполнима, и содержащей на одну переменную меньше. Мы оценим число операций, необходимых для такогоперехода.
Ясно, что число самих переходов не превосходит числа n переменных, от которых зависит исходная КНФ. Послеосуществления не более чем n − 1 переходов такого типа мы получим КНФ Kω , реализующую функцию одной переменной.Ее выполнимость устанавливается за число шагов, ограниченное константой. Таким образом доказательство будет состоятьв описании перехода от K к Kω и оценки числа шагов, достаточных для его осуществления.Кодирование КНФ. Буквы (т.е.
переменные и их отрицания) кодируются двоичными векторами длины dlog2 ne + 1, гдеn — наибольший индекс переменной в исходной КНФ. Первая координата вектора, являющегося кодом некоторой буквы,равна 1, если буква является переменной, и равна 0, если буква является отрицанием переменной. Остальные координатывектора представляют собой двоичную запись индекса переменной.
Символы (,), & и ∨ включаются в кодирующий алфавит.Таким образом, например, КНФ K = x1 &(x2 ∨ x̄3 ) кодируется словом W (K) = 101&(110 ∨ 011).Скобки считаются одинаковыми, если они совпадают или отличаются лишь порядком букв. Предполагается, что исходнаяКНФ не содержит одинаковых скобок и скобок вида (x ∨ x) и (x ∨ x̄).Если исходная КНФ K содержит l1 однобуквенных сомножителей и l2 двухбуквенных скобок, а наибольший индекспеременной в ней равен n, то длина L(W (K)) ее кода равна, очевидно, (l1 + 2l2 )(dlog2 ne + 1) + l1 + 2l2 − 1 = (l1 +2l2 )(dlog2 ne + 2) − 1.
Заметим, что число связок & и ∨ на единицу меньше числа букв.Выявление однобуквенных сомножителей. Если в КНФ K имеется однобуквенный сомножитель, то в подслове,состоящем только из связок & и ∨, встретятся два символа & подряд. Для обнаружения этой ситуации требуется порядкаL шагов, где L — длина слова W (K), кодирующего K.Случай, когда K содержит однобуквенные сомножители. В случае, когда буква x является однобуквенным сомножителем КНФ K, переход к КНФ K 0 осуществляется с помощью следующих преобразований:(a) x&x = x; (b) x&x̄&F = x&x̄; (c) x&(x ∨ y) = x; (d) x&(x̄ ∨ y) = x&y.После выполнения этих преобразований (а также преобразований, сводящихся к ним с использованием коммутативностиопераций & и ∨) полученная формула A содержит не более одного вхождения каждой из букв x и x̄.
При этом либоA = x&x̄, либо A = x, либо A = x&K 0 , где K 0 — КНФ, не зависящая от x. Ясно, что в первом случае исходная КНФне является выполнимой, во втором она выполнима, а в третьем она выполнима тогда и только тогда, когда выполнимаКНФ K 0 , не содержащая ни x, ни x̄. В первых двух случаях алгоритм заканчивает работу. В третьем получаем КНФ K 0 сменьшим числом переменных, чем исходная.Остается оценить число шагов, достаточное для осуществления соответствующих преобразований. Каждое из них сводится к нахождению кода буквы x или x̄, т.е. подслова длины dlog2 ne + 1, в коде КНФ K длины L и последующемвычеркивании его или замене всего слова на x&x̄. Нетрудно убедиться в том, что каждое из этих преобразований требует не более O(L log2 n) шагов на обычной (детерминированной) машине Тьюринга, а код КНФ K в код КНФ K 0 можнопреобразовать не более чем за O(L2 log2 n) ≤ O(L3 ) шагов.Случай, когда однобуквенные сомножители отсутствуют.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
