А.А. Сапоженко - Некоторые вопросы сложности алгоритмов (PDF) (1132758), страница 5
Текст из файла (страница 5)
Важным являетсято, что при фиксированных s и t число переменных, от которых зависят этиформулы, ограничено константой, зависящей только от НМТ. Поэтому послеперехода к КНФ получатся формулы ограниченной длины.Наконец, формула G утверждает, что на некотором шаге НМТ придет впринимающее заключительное состояние.
Пусть таковым является qr . ИмеемG = Qr1_Qr2_..._QrT .Нетрудно проверить, что построенная таким образом формула A обладаетвсеми требуемыми свойствами.2Список литературы[1] Кибернетический Сборник No 12 (Нов. серия), М. МИР, 1975, С. 5–10.[2] А. Ахо, Д. Хопкрофт, Д. Ульман// Построение и анализ вычислительныхалгоритмов, М., Мир, — 1979. — 536 С.[3] М.Гэри, Д.Джонсон, Вычислительные машины и труднорешаемые задачи, М., Мир, — 1982. — 416 С.[4] J. Edmonds, Paths, trees and flowers,// Canad. J.
Math., VIII, С. 449-467.[5] С. В. Яблонский “Введение в дискретную математику” М.: Наука, 1986.235О задачах выполнимости КНФПараграф посвящен некоторым разновидностям задач о выполнимости КНФ.Определим k-КНФ как конъюнкцию скобок, каждая из которых являетсядизъюнкцией не более k букв.
Задача k-ВЫП состоит в распознавании выполнимости произвольной k-КНФ. Здесь доказывается принадлежность задачиВЫП классу N P , полиномиальность задачи 2-ВЫП и N P -полнота задачи3-ВЫП.Пусть КНФ K зависит от переменных x1 , ..., xn (не обязательно существенно). Кодом КНФ K является слово W (K) в алфавите {0, 1, &, ∨}, полученное вычеркиванием символов скобок и заменой в K каждой буквы xσi двоичным вектором вида (σ, α1 , ..., αm ), где вектор (α1 , ..., αm ) является двоичнымразложением числа i, причем m = dlog ne.Теорема 5.1 Задача ВЫП∈ N PДоказательство.
Требуется доказать существование недетерминированной машины Тьюринга (сокращенно, НМТ), распознающей язык ВЫП. Определение НМТ дано выше (см. параграф 4). Содержательно говоря, алгоритмраспознавания выполнимости КНФ K состоит в следующем. Имея на входеКНФ K, НМТ µ строит две КНФ K0 и K1 , получающиеся из K путем подстановки вместо переменной x1 соответственно констант 0 и 1.
Затем НМТµ повторяет процедуру подстановки констант 0 и 1 вместо переменной x2 ит.д. Всякий раз НМТ µ прослеживает процесс подстановки параллельно (см.рис. 3).Рис.324В результате после осуществления n подстановок всякий раз будет получена некоторая КНФ с константами вместо переменных. Проверка равенства каждой из таких КНФ единице, очевидно, может быть осуществленадетерминированной машиной Тьюринга (а, значит, и НМТ) за время (числошагов), не превосходящее O(L), где L длина кода W (K). Если соответствующая КНФ равна единице, НМТ останавливается в принимающем состоянии,если КНФ равна нулю, то — в отвергающем.
КНФ K выполнима, если хотябы при одной подстановке констант НМТ останавливается в принимающемсостоянии.Нетрудно составить программу НМТ, которая, имея на входе код W (K)КНФ K, реализует описанные выше преобразования. НМТ будет иметь счетчик индексов переменных для того, чтобы знать, вместо какой переменной вданный момент подставляются константы.
Выработать код индекса переменной на очередном шаге можно, прибавив 1 к двоичному счетчику индексов.Для этого требуется не более O(m) = O(log n) шагов.Подстановку константы вместо буквы xσi можно представлять себе какподстановку специальных символов 0∗ и 1∗ вместо первой координаты кодабуквы xσi . При этом мы полагаем, что символы 0∗ и 1∗ входят в алфавитНМТ и отличны от символов 0 и 1, используемых для кодирования индексовпеременных. Осуществляя преобразования, связанные с подстановкой констант вместо переменной xi , НМТ сначала делает выбор, какую из константподставлять (недетерминированная часть i-го этапа), а затем подстановкаосуществляется детерминированным алгоритмом.
Именно, следует отыскатьв слове код очередной буквы вида xσi и заменить его первый разряд однимиз двух символов 0∗ и 1∗ . Для распознавания того, что заданное подсловодлины m = dlog ne слова W длины L совпадает с двоичной записью числа i,хранящейся на ленте, скажем, непосредственно перед самим словом, достаточно O(mL) шагов. Число таких замен не превосходит L. Таким образом,при заданном коде индекса переменной замену последней на константу можно осуществить не более чем за O(L2 log n) шагов. Ясно, что число шагов вкаждом вычислении не превосходит O(nL2 log n) = O(L3 ), где L длина входа.
За это время НМТ придет в некоторое заключительное состояние. Еслисреди заключительных состояний окажется хотя бы одно принимающее, тоКНФ K выполнима. В противном случае она не является выполнимой. Такимобразом, построенная НМТ распознает язык ВЫП за время O(L3 ).2Следствие 5.1 Задача ВЫП является N P -полной.Утверждение следует из теоремы Кука и теоремы 5.1.25Определим задачу k-ВЫП ее входом и свойством.ВХОД: F (x1 , . . . , xn ) — 3-КНФ.СВОЙСТВО: выполнимость.Теорема 5.2 2-ВЫП ∈ P .Доказательство. Мы представим полиномиальный алгоритм распознавания 2-выполнимости. Идея алгоритма сотоит в переходе от КНФ K, выполнимость которой требуется установить, к новой КНФ K 0 , выполнимой тогдаи только тогда, когда K выполнима, и содержащей на одну переменную меньше.
Мы оценим число операций, необходимых для такого перехода. Ясно, чточисло самих переходов не превосходит числа n переменных, от которых зависит исходная КНФ. После осуществления не более чем n − 2 переходов такоготипа мы получим КНФ Kω , реализующую функцию одной переменной. Еевыполнимость устанавливается за число шагов, ограниченное константой.Таким образом доказательство будет состоять в описании перехода от K кKω и оценки числа шагов, достаточных для его осуществления.Кодирование КНФ. Буквы (т.е. переменные и их отрицания) кодируются двоичныим векторами длины dlog 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 )(dlog ne + 1) + l1 + 2l2 − 1 =(l1 + 2l2 )(dlog ne + 2) − 1. Заметим, что число связок & и ∨ на единицу меньшечисла букв.Выявление однобуквенных сомножителей. Если в КНФ K имеется однобуквенный сомножитель, то в подслове, состоящем только из связок& и ∨, встретятся два символа & подряд.
Для обнаружения этой ситуациитребуется порядка L шагов, где L — длина слова W (K), кодирующего K.Случай, когда K содержит однобуквенные сомножители. В случае, когда буква x является однобуквенным сомножителем КНФ K, переход26к КНФ 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̄, т.е. подслова длины dlog ne+1, в коде КНФ K длины L и последующем вычеркивании его или замене всего слова на x&x̄. Нетрудно убедитьсяв том, что каждое из этих преобразований требует не более O(L log n) шагов на обычной (детерминированной) машине Тьюринга, а код КНФ K в кодКНФ K 0 можно преобразовать не более чем за O(L2 log n) ≤ O(L3 ) шагов.Случай, когда однобуквенные сомножители отсутствуют. ПустьКНФ K не содержит однобуквенных сомножителей.
Тогда переход к K 0 осуществляется следующим образом. Выбираем некоторую букву x в КНФ K.Пусть K0 представляет собой конъюнкцию всех дизъюнкций вида (x̄ ∨ y),где y — некоторая буква, отличная от x и x̄, входящих в K, K1 представляет собой конъюнкцию всех дизъюнкций вида (x ∨ y), входящих в K, а K2представляет собой конъюнкцию всех остальных дизъюнкций, входящих вVK. Таким образом, КНФ K0 представима в виде K0 = 1≤i≤k (x̄ ∨ yi ), а K1Vпредставима в виде K1 = 1≤j≤m (x̄ ∨ zj ).
Заметим, чтоK0 K1 K2 = (x̄ ∨ y1 ...yk )(x ∨ z1 ...zm )K2 .(14)Легко проверить, что формула (x̄ ∨ Y )(x ∨ Z), в которой Y и Z не зависятот x, выполнима тогда и только тогда, когда выполнима формула Y ∨ Z.С учетом того, что K2 не зависит от x, аналогично получаем, что праваячасть (14) выполнима тогда и только тогда, когда выполнима формула(y1 ...yk ∨ z1 ...zm )K2 =^^(yi ∨ zj )K2 = K 0 .(15)1≤i≤k 1≤j≤mКНФ K 0 не содержит x и x̄, а число букв в ней не больше L2 , где L — число букв в W (K). Нетрудно построить машину Тьюринга, преобразующую27W (K) в W (K 0 ) за O(L3 ) шагов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
