В.Б. Алексеев - Введение в теорию сложности алгоритмов, страница 12

Лемма 4.1 т. При условии, чтао набор переменных хвд, уе, гьв коррекшно задает конфигурацию Кв, таста факт, что Кв являетпся правильной начальной конфигурацией для пары (а, б), где а — заданное слово и б Е В* — какое-нибудь слово длины не более о(п), можно выразить в виде КНФ Рз длиньь не более рз(п), где рт — некотаорый полипом. Доказатаельставо. Пусть а = дт,дй...д~„и о е В', где В = (д„„дтю..., 4,„1.

Тогда указанный в лемме фант выражается формулой ог = уо2с48схо„;8сх)м2с... Йх„т 8сх„д Й Последняя скобка х( е Ч хьы в — — хт о -+ х; т о означает, что если в ячейке т стоит пустой символ, то и в следующей ячейке должен стоять пустой символ, то есть слово 6 не может;иметь разрывов. Формула Рз является КНФ с длиной и + 3+ р(п) + о(п) ° (ю + 1) + р(п) — и — о(п) + (о(п) — 1) 2 < рз(п), где рз — некоторый.

полинам. Следующее утверждение очевидно. Лемма 4.18. Тоти фактт~) чтпо в К („) состпояние есть дв, выражаетпся в виде КНФ Гз = го " . (») Рассмотрим теперь более подробно программу машины М. Представим ее команды в виде ((т()ь -ь Ы„(( ь)ов(( ь)Н(у, й), где Н(у, й) = — 1, () или 1 соответственно, для сдвига влево, оставления головки на месте и сдвига вправо.

Лемма 4.19. При условии, чтло набор переменных х,', у,', гь корректпно задаетп конфигурации Ко, Кь..., Кр(„), тлотп факт, чтпо каждая конфигурация Ктчл получаепься из К по программе машины М, можно выразиспь в виде Ксз'Ф Г4 длины не более рс(п), еде р4 неноспорыа полинам. л1онаэашельсспво. Этот факт выражается формулой с+с с+с сьс УЮ ЕУЮ У'+Ябь1 Первая часть этой формулы выражает изменение информации в обозреваемой ячейке, изменение состояния н сдвиг головки, вторая часть выражает тот факт, что символы во всех ячейках, кроме обозреваемой, не изменяются.

Выражение в первой скобке в Гл — это функция от 6 переменных и ее (как любую функцию алгебры логики, отличную от южстанты 1) можно представить в виде КНФ некоторой длины Е~. Аналогично можно представить в виде КНФ константной длины Ьз функцию от 2сп + 1 переменных, стоящую во второй скобке. При этом Гс преобразуется в КНФ Кл длины р(п) ° (2р(п) + 1) ° сп ° 1 ° 1п + р(п) .

(2р(п) + 1) . с з ( рл(п), где р4 — некоторый полинам. Положим Гв — — Гс Гз Гз Г4. Тогда Гв — КНФ и по леммам 4.16-4.19 на наборе переменных т,';, у,', еьс она истинна тогда н только тогда, когда переменные корректно задают некоторое вычисление машины М, приводюцее в состояние 4в = "да", для входной пары (а, Ь), где Ь вЂ” какое-нибудь слово нз В' такое, гго /Ь| < д(1а!).

Таким образом Ге истинна хотя бы на одном наборе (т,е. выполнима) в том и только в том случае, если истинна правая часть в (4.3) и, следовательно, если а Е Е. Получаем, что Ге — искомэл КНФ. Ее длина не превосходит некоторого полинома от и. При этом нетрудно понять, что по данному слову а (и фиксированной программе машины М) эта КНФ Гв = Гс . Гз Гз Гс выписывается за время, ограниченное полиномом от ее длины, и, следовательно, ограниченное полиномом от длины слова а.

Таким образом, отображение а -+ Ге является полиномиальным сведением язьпса 1 к языку ВЫП. Поскольку Ь— произвольный язык из ссР, то получаем, что ВЫП вЂ” МР-трудная задача, а так как ВЫП е с"сР (см. и. 4.5), то ВЫП вЂ” ссР-полная задача. Теорема Кука доказана. 4.7. Сложность задаг о выполнимости Следующая теорема позволяет выводить с с Р-полноту одних задач из 1ссР-полноты других задач, Теорема 4.13.

Если Ь1 — МР-тпрудный язык и Ь1 полинольиально сводится к языку Ьз, то Ьз — ХР-гаруднььй язык. Если нри этлож Ьр б МР, лю Ьз — ИР-лолный лэык. ,Покаэагаельстпво. Пусть Ь вЂ” любой язык из МР. Так как Е1 — ИР-трудный язык, то Ь полиномиально сводится к Ьь При этом, если длина исходного слова равна н, то при сведении оно переходит в слово длины не более д(и), где д — некоторый полинам. Так как по условию Ь1 сводится к Вз за время, полиномиально зависящее от длины сводимого слова, то композипня двух сведений полиномиально сводит Ь к Ьз. Так как Ь вЂ” произвольный язык из ХР, то Ла — ХР трудный язык по определению. Определение.

КНФ, у которой в каждом дизъюнкте ровно 3 различных литерала, будем называть З-КНФ. Задача 3-выполнимость (З-ВЫП). Входной алфавит тот же, что и в задаче ВЫП. Вопрос: верно ли, что входное слово — это З-КНФ, хоторвя выполнима. Ъ'твервсдение. 3-ВЫП Е ИР. Покаэательсозво. Задача 3-ВЫП удовлетворяет определению залач из класса ХР.

При этом в качестве сертификата достаточно взять набор а, на котором данная 3-КНФ выполнима (если такой существует), а алгоритм проверки сертификата будет проверять, действительно ли входное слово есть 3-КНФ и верно ли, что эта КНФ на наборе а равна 1. Все это можно осуществить за полиномиэльное (от длины входа) время. Теорема 4.14. Задача 3-ВЫП ХР-полна. Яоказапьвльсоьво. Сведем задачу ВЫП полиномиально к задаче 3-ВЫП.

Пусть А — алфавит обеих задач. Нам надо для каждого слова а б А' за полиномиальное (от длины слова а) время построить слово у(а) так, чтобы у(а) было выполнимой 3-КНФ тогда и только тогда, хогда а — выполнимая КНФ. Если а й А' не КНФ, то положим ~в(а) = а. Если же а — КНФ .Рь Рз ... Р, от переменных хп хз,, х„, то преобразуем ее в 3-КНФ ~р(а) = Рпрз ... Р, следующим образом. Пусть У = 1уы уз,... 1 — некоторые переменные, которые не встречаются в КНФ а.

Рассмотрим 4 случая. . 1) Если .0; = $щ Ч ЦдЧ Цд, то положим Р, = Рь 2) Если Р; = 1ь1Ч1; з, то положим Р; = (111ЧРцзЧу ) ~111 Ч~дЧуд) где у. б У. Заметим, что Р; = 1 ~=; .0; = 1. 3) Если Р» = го то положим Г» = (», ч уг ч у») (Ф, ч уг ч у») (1, ч уг ч у») (г» ч уь у у»), где уз ,-Е уь Опять Г» = 1 л=э Р; = 1. 4) Пусть Р~ — — »» Ч»г '4...

Ч $,„и т ) 4. Положим Р» = (1~ р»г Чу»)(у» М ге»»уг)(уг У»» Муз) . ' (Уы-4 Ч»ы-г У уы-З)(уы-3 '4 »па-д Ч»чп), где все уу различны. Лемма 4.20. В случае 4), если Р, = 1, то и Р» = 1, а если Р» = 1, то суи»ествует набор значений переменных ум уз,...,у~ з такой, что Р; = 1. л»оказательство. Пусть»1 = (ап..., о„) — набор значеввй переменных хь..., х„из Р; и ф = (Д,..., Д з) — набор значений переменных ры, р з.

Пусть Р»(б, В) = 1, то есть все скобки в Р» на наборе (б, ф) равны 1. Если В» = О, то»»(б) у гг(б) = 1 и Р;(б) = 1. Если Д -э=1,то~ »(»1)Чг„,(»1) =1иР»(б) =1. Еспиже»3» =1иД„э = О, то найдется lс такое, что 13з = 1, »3э+г = О. Так как $эч ге+э(»г) чае+; = 1, то в этом случае гь»г(»1) = 1 и Р»(с») =.1: Спедовательно, если Р» = 1, то и 'Р» = 1. Обратно пусть Р»(б) = 1.

Тогда существует»ь тахое, что 1з(»г) = 1. Если й = 1 иди к = 2, то выберем 13» = 13г = ... = Д„з = О. При этом Р»(»1,»3) = 1. Если и = »и — 1 или к = т, то выберем 13» = 13г = ... = Д„з = 1. При этом опять Р»(а, ф) = 1. В остальных слУчаЯх положим 13» = 13г = ... = 13ь г = 1, »3з» = Вэ =... = Д„з = О. Снова получим Р»(»г, »3) = 1. Лемма доказана. Проделаем указанные выше в пунктах 2)-4) замены Р» на Ро испопьзуя дпя рваных Р» разные переменные у . Тогда по лемме 4.20 получаем, что если 3-КНФ Р» Гг ... Г, равна 1 на каком-то наборе, то на том же наборе равна 1 и КНФ Р» Рг ... Р„и обратно, если КНФ Рг - Рг . Р, равна 1 на некотором наборе, то существует набор, на котором 3-КНФ Г» Рг °...

Г, также равна 1. Таким образом 3-КНФ Гг Гг °... Р, выполнима тогда и только тогда, когда выполнима КНФ Ры Рг... Р„то есть наше преобразование является сведением задачи ВЫП к задаче З-ВЫП. Распознать, явпяется ви входное слово а й А' КНФ можно за попвномиапьное от двины а время. Преобразовать все Р» в Х» также можно за попиномиапьное время. Поэтому мы имеем полиномиапьное сведение задачи ВЫП к задаче 3-ВЫП. Поскольку задача ВЫП является ФР-полной и 3-ВЬГП й МР, то по теореме 4.13 получаем, что задача 3-ВЫП является 1ч'Р-подвой. зв Посмотрим, нельзя ли в последней теореме заменить 3 на 2. Определение. КНФ, у которой в каждом дизъюнкте не более 2 литералов, будем называть 2-КНФ. Задача 2-выполнимость (2-ВЫП).

Входной алфавит тот же, что и в задаче ВЫП. Вопрос: верно ли, что входное слово — это 2-КНФ, которая выполнима. Теорема 4.1б. Ялз задачи 2-ВЫП су~цестпвуетп алзоритпн с поликомиальное сложностпью (тпо есть 2-ВЫП б Р). Показатпельстпво. Проверить, является ли входное слово 2-КНФ, можно за полиномиальное время. Поэтому будем считать, что нам уже дана 2-КНФ Рт Рз ... Р, и требуется выяснить, выполнима пи ова. Пусть дизъюнкты Р' = х; Ч тт и Рп = х; Ч сз имеют противоположные литералы хт и х, (при этом может быть ст = ю или 6э = то).

Тогда рвзольвентпоб дизъюнктов Р' и Р" по х; будем называть дизъюнкт Р = 8т Ч сз (если Ет = сз, то Мт Ч 1з = Ст). Если Ст = й и Мз = И, то положим Р ы О. Лемма 4.21. Дот любых формул А и В вмполняетпся равекстпво (хт Ч А)(хт Ч В) = (х, Ч А) х, Ч В) (А Ч В). Яоказатпельситво. Если правая часть равна 1, то, очевидно, и левая часть равна 1. Если правая часть равна О, то либо х, Ч А = О, либо х; Ч В = О, либо А Ч В = О. В первых двух случаях левая часть равна О. В последнем случае А = 0 и В = О.

Тогда левая часть равна (х; Ч 0)(х, Ч 0) = х,хт = О. Лемма доказана. Эта лемма локэзывает, что добавление к 2-КНФ резольвенты лк бой пары дизъюнктов не меняет функцию, реализуемую 2-КНФ. Будем просматривать все пары дизъюнктов текущей 2-КНФ и строить их реюльвенты. Если окажется, что некоторая резольвента отсутствует в текущей 2-КНФ, то добавим ее и начнем просмотр сначала.

Так будем делать до тех пор, пока не окажется, что все резольвенты текущей 2-КНФ уже содержатся в ней. Если при этом будет порождена резольвенга О, то выдаем ответ: "Исходная 2-КНФ невыполнима", иначе выдаем ответ: "Исходная 2-КНФ выполнима". Лемма 4.22. Алгоритпм обязатпельно остпановитпсл и работпаетп иолиномиальное время. Яоиазатпельстпво.