А.А. Сапоженко - Некоторые вопросы сложности алгоритмов, страница 7

. , Sih , } является покрытием множества S (т.е. ∪Sj ∈T = S) тогда и только тогда, когдасоответствующее подмножество вершин {i1 , . . . , ih } графа G0 = (V 0 , E 0 ) покрывает все ребра. Отсюда следует, что свойствазадач ВЕРШИННОЕ ПОКРЫТИЕ и ПОКРЫТИЕ МНОЖЕСТВ выполняются или не выполняются одновременно.2Задача РАСКРАСКА:ВХОД: Граф G = (V, E) и число k.СВОЙСТВО: Cуществует функция ϕ : V → Zk такая, что ϕ(u) 6= ϕ(v) для всех (u, v) ∈ E.Теорема 6.5 3-ВЫПОЛНИМОСТЬ ≺ РАСКРАСКА.20Доказательство.Пусть формула K представляет собой 3-КНФ с n переменными и t сомножителями (скобками). Покажем как построить завремя, ограниченное полиномом от max(n, t), граф G = (V, E) с 3n + t вершинами, который можно раскрасить в n + 1 цветовтогда и только тогда, когда КНФ K выполнима.Пуcть x1 , x2 , .

. . , xn и C1 , C2 , . . . , Ct — соответственно переменные и сомножители КНФ K. Пусть v1 , v2 , . . . , vn — новыесимволы. Без потери общности будем считать, что n ≥ 4, поскольку любую КНФ, число различных переменных которой непревосходит 3, можно проверить на выполнимость за время, линейно зависящее от ее длины, не прибегая к раскраске.Вершины графа G таковы:1. xi , x̄i , vi для 1 ≤ i ≤ n,2. Ci для 1 ≤ i ≤ t.Ребрами графа G являются1.

все (vi , vj ), для которых i 6= j,2. все (vi , xj ) и (vi , x̄j ), для которых i 6= j,3. (xi , x̄i ) для 1 ≤ i ≤ n,4. (xi , Cj ), если xi не входит в Cj , и (x̄i , Cj ), если x̄i не входит в Cj .Вершины v1 , v2 , . . . , vn образуют полный граф с n вершинами, так что для их раскраски требуется n различных цветов.Каждая из вершин xj и x̄j соединена с каждой вершиной vi , i 6= j и, значит, xj и x̄j не могут быть того же цвета, что и vi ,если i 6= j.

Так как вершины xj и x̄j смежны, то они не могут быть одинакогого цвета, и потому граф G можно раскраситьв n + 1 цветов только тогда, когда одна из вершин xj и x̄j имеет тот же цвет, что и vj , а другая имет новый цвет, которыймы назовем специальным.Пусть той из вершин xj и x̄j , которая раскрашена в специальный цвет, приписано значение 0. Рассмотрим цвет, приписанный вершинам Cj . Вершина Cj смежна по крайней мере с 2n − 3 из 2n вершин x1 , x2 , .

. . , xn , x̄1 , x̄2 , . . . , x̄n . Так как мыпредположили, что n ≥ 4, то для каждого j найдется такое i, что вершина Cj смежна как с xi , так и с x̄i . Поскольку однаиз вершин xi или x̄i раскрашена в специальный цвет, то Cj не может быть раскрашена в специальный цвет. Если скобкаCj содержит такой символ y, что вершине ȳ приписан специальный цвет, то вершина Cj не смежна ни с какой вершиной,раскрашенной так же, как y, и, значит, ей можно приписать тот же цвет, что и у вершины y. В противном случае нуженновый цвет.Таким образом, все вершины Ci можно раскрасить без дополнительных цветов тогда и только тогда, когда символамможно так приписать специальный цвет, чтобы каждый сомножитель содержал такой символ y, что символу ȳ приписанспециальный цвет, т.е.

тогда и только тогда, когда переменным можно так присвоить значения, чтобы в каждом сомножителеоказался y со значением 1 (ȳ со значением 0), т.е. тогда и только тогда, когда КНФ C выполнима.2Пример. Пусть K = (x1 ∨ x2 )(x̄1 ∨ x3 ). Граф, соответствующий данному входу задачи 3-ВЫП, показан на рис. 6.4.Указанная на нем раскраска в цвета A, B, C и дополнительный цвет S соответствует набору (010), обращающему КНФ Kв единицу.21Рис. 6.4Список литературы[1] Кибернетический сборник (Нов.

серия), No 12 , М.: МИР, 1975, С. 5–10.[2] А. Ахо, Д. Хопкрофт, Д. Ульман// Построение и анализ вычислительных алгоритмов, М.: Мир, 1979, 536 С.227 Теорема СэвиджаВ этом параграфе устанавливается связь между сложностью булевых функций и временн́ой сложностью машинных вычислений. Наличие такой связи может показаться неожиданным, поскольку схемная сложность ассоциируется скорее сописательной сложностью, нежели со сложностью вычислений.

Тем не менее, как мы увидим, сложность схемы из функциональных элементов хорошо мажорирует время машинных вычислений. Это и утверждает теорема Дж. Сэвиджа [1].Доступное для отечественного читателя изложение (которому мы здесь в основном следуем) можно найти также в [2].Рассматриваются обычные (детерминированные) машины Тьюринга c односторонней бесконечной вправо лентой, алфавитом ленты A = {a1 , .

. . , am } и алфавитом состояний Q = {q0 , . . . qk }. Начальное состояние обозначается через q0 , азаключительное — через qk . Один из символов ленты называется пустым и обозначается через Λ. Он обозначает отсутствие значащего символа в ячейке ленты. Другие понятия, касающиеся машин Тьюринга, даны в параграфе 4. В начальныймомент на ленте записано исходное слово x1 , x2 , . . . , xn и головка обозревает самый левый символ этого слова в состоянииq0 .

Все остальные ячейки заполнены символом Λ.Прежде чем перейти к непосредственному моделированию машины Тьюринга схемами, отметим ряд обстоятельств,затрудняющих сравнение. Прежде всего, машины Тьюринга допускают входные слова произвольной длины, в то время каксхемы — только слова фиксированной длины. Далее, машины Тьюринга к некоторым входным словам не применимы, тогдакак схема определена на каждом входном слове.

Время работы машины Тьюринга, вообще говоря, не ограничено никакойобщерекурсивной функцией, в то время как минимальные схемы имеют ограниченную сложность.Мы будем применять для моделирования обобщенные схемы из функциональных элементов, у которых на входах иe где A — ленточный алфавит, Qe = Q ∪ {q̃}, Q — алфавит состояний, q̃ —выходах элементов — символы алфавитов A и Q,новый символ, который называется холостым состоянием.Ясно, что каждый такой элемент можно моделировать обычной (двоичной) схемой константной сложности после предe конечными двоичными последовательностями.

Поэтому переход от обобварительного кодирования букв алфавитов A и Qщенных схем к обычным связан с увеличением сложности лишь в константу раз. Итак, пусть машина Тьюринга M работаетна каждом слове длины n не более T тактов.Рис. 7.1Построим обобщенную схему, которая моделирует работу M на словах длины n.

Схема строится из преобразующихэлементов U и фильтрующих элементов Φ. Элемент U имеет два входа и четыре выхода (см. рис. 7.1).e Если qj = q̃, то элемент U производит тождественноеНа левый вход подаются символы ai ∈ A, на правый qj ∈ Q.преобразование, т.е.a0 i = ai ,qjR = qjL = qjS = q̃.Если qj 6= q̃, то в системе команд машины M отыскиваем команду с левой частью ai qj . Пусть ее правая часть естьal qm L. Тогда на выходе элемента Ua0 i = al ,qjL = q 0 m ,23qjR = qjS = q̃.Если символ движения головки L заменить на S или R, то, соответственно, будет qjS = qm или qjR = qm , а на другихq-выходах q̃.e Если на одном из входов q 1 , q 2 , q 3На входах и выходе элемента Φ (см. рис. 7.1) возникают только символы алфавита Q.появляется символ, отличный от q̃, то он проходит на выход (случай, когда несколько входов отличны от q̃, невомозжен).Если на всех входах появляется q̃, то выход равен q̃.Заметим, что если время работы МТ над словом x1 .

. . xn не превосходит T , то головка может уйти вправо от начальногоположения не далее, чем на T ячеек. Поэтому достаточно держать в поле зрения зону ленты из T ячеек, которые мы будемнумеровать числами от 1 до T . Схема, которую мы построим, имеет прямоугольный вид. У нее T (двухъярусных) строк иT столбцов. При этом i-ая строка (i = 1, 2, . . . , T ) выходами своих T элементов представляет i-ую конфигурацию машиныM , а именно, элемент U j-го (1 ≤ j ≤ T ) столбца — символ, содержащийся в j-ой ячейке, а элемент Φ — состояниемашины, обозревающей j-ю ячейку.

При всяком i в точности для одного j состояние отлично от q̃ (а именно, для тойячейки, которая действительно обозревается головкой в i-й конфигурации). Для всех остальных ячеек элемент Φ выдаетзначение q̃ (холостое состояние). На пересечении i-й строки и j-ого столбца в схеме один элемент U и один элемент Φ.Мы будем изображать их один под другим, тем самым каждая строка будет двухъярусной. Порядок соединения элементовпоказан на рис. 7.2.Рис. 7.2Для наглядности на том же рисунке сверху показан фрагмент текущей конфигурации, а на входах элементов — соответствующие значения схемы в предположении, что команда машины M имеет вид ai qj → a0 i q 0 j L.Теорема 7.1 (Дж.Сэвидж) Пусть машина Тьюринга M работает на словах длины n не более TM (n) тактов.

Тогда ее2можно моделировать схемой из функциональных элементов сложности O(TM(n)).Доказательство. Построенная нами схема из обобщенных элементов моделирует работу машины M . Фактически онавоспроизводит последовательность конфигураций при работе машины над входным словом. Из построения ясно, что схемасодержит 2T 2 обобщенных элементов. После замены каждого такого элемента схемой из двоичных элементов сложностьвозрастает только в константу раз.224Примечание. Легко видеть, что в построенной схеме много "лишних"элементов. Это, например, элементы правоговерхнего угла схемы, где длительное время состояние остается холостым.

И в оставшейся части схемы существенны толькоэлементы в окрестности нехолостого значения состояния. Это предоставляет большие возможности для упрощения схемы.К.П.Шнорр [3] понизил верхнюю оценку до O(TM (n) log SM (n) + kM k), где TM (n) и SM (n) соответственно число тактов ичисло ячеек, достаточное для обработки слова длины n машиной Тьюринга, а kM k — число команд машины M .Список литературы[1] J.E.Savage, Computational work and time on finite machines, J. Ass. Comp. Mach., 1972, v. 19, p. 660-674.[2] Р.Г.Нигматуллин, Сложность булевых функций, Издательство Казанского университета, 1983, 208 c.[3] C.P.Schnorr, The network complexity and the Turing machine complexity of finite functions. Acta Informatica, 1976, v.

7, p.95-107.258 Содержание1. Введение12. Алгоритмические трудности синтеза схем23. Локальные алгоритмы64. Теорема Кука125. N P -полнота задач k-ВЫП156. Некоторые N P -полные задачи187. Теорема Сэвиджа2326.