А.А. Сапоженко - Некоторые вопросы сложности алгоритмов (PDF) (1132758), страница 7
Текст из файла (страница 7)
Поэтому всякое ребро из Ḡ инцидентно хотя быодной вершине из V \ A. Аналогично, если V \ A является вершинным покрытием графа Ḡ, то каждое ребро из Ḡ инцидентно хотя бы одной вершинеиз V \ A. Поэтому никакое ребро не соединяет две вершины из A, а, значит,A — клика в G.2Рис.633Пример. Граф G с множеством вершин {1, 2, 3, 4} (см. рис.
6) содержитклику {1, 2, 3}. В графе G дополнение этого множества покрывает все ребра.Задача ПОКРЫТИЕ МНОЖЕСТВ:ВХОД: Семейство F = {S1 , . . . , Sm } подмножеств множества S такое,что ∪Sj ∈F = S, и число h.СВОЙСТВО: Cуществует подсемейство T ⊆ F такое, что |T | ≤ h и приэтом ∪Sj ∈T = S.Теорема 6.4 ВЕРШИННОЕ ПОКРЫТИЕ ≺ ПОКРЫТИЕ МНОЖЕСТВ.Доказательство.Пусть задан вход задачи ВЕРШИННОЕ ПОКРЫТИЕ: граф G0 = (V 0 , E 0 ) ичисло l. ПоложимS = E 0 , Sj = {< u, vj >∈ E 0 : u ∈ V 0 }, и h = l.Очевидно, подсемейство T = {Si1 , . .
. , 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-ВЫПОЛНИМОСТЬ ≺ РАСКРАСКА.Доказательство.Пусть формула 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 таковы:341. 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соединена с каждой вершиной vj , i 6= j и, значит, xj и x̄j не могут быть тогоже цвета, что и vi , если i 6= j.
Так как вершины xj и x̄j смежны, то они немогут быть одинакогого цвета, и потому граф G можно раскрасить в n + 1цветов только тогда, когда одна из вершин xj и x̄j имеет тот же цвет, что иvj , а другая имет новый цвет, который мы назовем специальным.Пусть той из вершин xj и x̄j , которая раскрашена в специальный цвет.Рассмотрим цвет, приписанный вершинам 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-ВЫП, показан на рис. 7. Указанная на нем раскраска в цветаA, B, C и дополнительный цвет S соответствует набору (010), обращающемуКНФ K в единицу.35Рис.7Список литературы[1] Кибернетический Сборник No 12 (Нов.
серия), М. МИР, 1975, С. 5–10.[2] А. Ахо, Д. Хопкрофт, Д. Ульман// Построение и анализ вычислительныхалгоритмов, М., Мир, — 1979. — С. 420–428.367Теорема СэвиджаВ этом параграфе устанавливается связь между сложностью булевых функций и временн́ой сложностью машинных вычислений. Наличие такой связиможет показаться неожиданным, поскольку схемная сложность ассоциируется скорее с описательной сложностью, нежели со сложностью вычислений.Тем не менее, как мы увидим, сложность схемы из функциональных элементов хорошо мажорирует время машинных вычислений.
Это и утверждаеттеорема Дж. Сэвиджа [1]. Доступное для отечественного читателя изложение (которому мы здесь в основном следуем) можно найти также в [2].Рассматриваются обычные (детерминированные) машины Тьюринга cодносторонней бесконечной вправо лентой, алфавитом ленты A = {a1 , . . . , am }и алфавитом состояний Q = {q0 , . . . qk }. Начальное состояние обозначаетсячерез q0 , а заключительное — через qk .
Один из символов ленты называется пустым и обозначается через Λ. Он обозначает отсутствие значащегосимвола в ячейке ленты. Другие понятия, касающиеся машин Тьюринга, даны в параграфе 4. В начальный момент на ленте записано исходное словоx1 , x2 , . . . , xn и головка обозревает самый левый символ этого слова в состоянии q0 . Все остальные ячейки заполнены символом Λ.Прежде чем перейти к непосредственному моделированию машины Тьюринга схемами, отметим ряд обстоятельств, затрудняющих сравнение. Прежде всего, машины Тьюринга допускают входные слова произвольной длины,в то время как схемы — только слова фиксированной длины. Далее, машины Тьюринга к некоторым входным словам не применимы, тогда как схемаопределена на каждом входном слове.
Время работы машины Тьюринга, вообще говоря, не ограничено никакой общерекурсивной функцией, в то времякак минимальные схемы имеют ограниченную сложность.Мы будем применять для моделирования обобщенные схемы из функциональных элементов, у которых на входах и выходах элементов — символыe где A — ленточный алфавит, Qe = Q ∪ {q̃}, Q — алфавиталфавитов A и Q,состояний, q̃ — новый символ, который называется холостым состоянием.Ясно, что каждый такой элемент можно моделировать обычной (двоичной) схемой константной сложности после предварительного кодированияe конечными двоичными последовательностями.
Поэтобукв алфавитов A и Qму переход от обобщенных схем к обычным связан с увеличением сложностилишь в константу раз. Итак, пусть машина Тьюринга M работает на словахдлины n не более T тактов.37Рис.8Построим обобщенную схему, которая моделирует работу M на словахдлины n. Схема строится из преобразующих элементов U и фильтрующихэлементов Ф . Элемент U имеет два входа и четыре выхода (см. рис. 8).e Если q = q̃,На левый вход подаются символы ai ∈ A, на правый qj ∈ Q.jто элемент U производит тождественное преобразование, т.е.a0 i = a0 l ,qjR = qjL = qjS = q̃.Если qj 6= q̃, то в системе команд машины M отыскиваем команду с левойчастью ai qj .
Пусть ее правая часть есть a0 i q 0 j L. Тогда на выходе элемента Ua0 i = a0 l ,qjL = q 0 j ,qjR = qjS = q̃.Если символ движения головки L заменить на S или R, то, соответственно,будет qjS = q 0 j или qjR = q 0 j , а на других q-выходах q̃.eНа входах и выходе элемента Ф возникают только символы алфавита Q.Если на одном из входов q 1 , q 2 , q 3 появляется символ, отличный от q̃, то онпроходит на выход (случай, когда несколько входов отличны от q̃, невомозжен). Если на всех входах появляется q̃, то выход равен q̃.Заметим, что если время работы МТ над словом x1 . .
. xn не превосходит T , то головка может уйти вправо от начального положения не далее,чем на T ячеек. Поэтому достаточно держать в поле зрения зону ленты изT ячеек, которые мы будем нумеровать числами от 1 до T . Схема, которуюмы построим, имеет прямоугольный вид. У нее T (двухярусных) строк и Tстолбцов. При этом i-ая строка (i = 1, 2, . . . , T ) выходами своих T элементов представляет i-ую конфигурацию машины M , а именно, элемент U j-го38(1 ≤ j ≤ T ) столбца — символ, содержащийся в j-ой ячейке, а элемент Ф— состояние машины, обозревающей j-ю ячейку.
При всяком i в точностидля одного j состояние отлично от q̃ (а именно, для той ячейки, которая действительно обозревается головкой в i-й конфигурации). Для всех остальныхячеек элемент Ф выдает значение q̃ (холостое состояние). На пересечении i-йстороки и j-ого столбца в схеме один элемент U и один элемент Ф . Мы будемизображать их один под другим, тем самым каждая строка будет двухярусной. Порядок соединения элементов показан на рис.9.Рис.9Для наглядности на том же рисунке сверху показан фрагмент текущейконфигурации, а на входах элементов — соответствующие значения схемы впредположении, что команда машины M имеет вид ai qj → a0 i q 0 j L.Теорема 7.1 (Дж.Сэвидж) Пусть машина Тьюринга M работает на словах длины n не более TM (n) тактов. Тогда ее можно моделировать схемой2(n)).из функциональных элементов сложности O(TM39Доказательство.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
