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

Цля распознавания справедливости такого свойства О легко построить алгоритм со сложностью, не превосходящей полинома от суммарной длвны кода формулы Р и кода набора (аь...,а ). Еще раз обсудим вопрос о представлении входных данных. Мы ве можем, например, вюпочнть в алфавит А произвольные переменные, так как их бесконечное число, а любая машина Тьюринга работает лишь с конечными алфавитами.

Однако достаточно взять алфавит А = (х,О, 1, Й, ~/, ~(, (, )) и переменную х; записывать как х с влущим далее числом ь', представленным в двоичной системе счисления. Обратим также внимание на то, что в определевни задач распознавания на вход может поступить любое слово в заданном алфавите А.

В задаче ВЫП многие такие слова не представляют КНФ. Предполагается, что ответом для таких входных слов явпяется "нет". Аналогично понимаются и другие задачи (напрнмер, КЛИКА или ГЦ). Теорема 4.11. Р С ХР" Показатеаьстео. Пусть В Е Р, и В С А'. Возьмем любой алфавит В и д(п) = 1. Предикат Я(а, Ь) пусть выражает тот факт, что а Е Е (независимо от Ь). Так как Ь Е Р, то преднкат ( > распознается за время, полиномиально зависящее от )а), а значит и от )а! + )Ь|, то есть Я Е Р.

При этом, очевидно, что для любого а Е А' справедливо соотношение а Е В с=» 3Ь Е В'()Ь! ( 1Ю(а Ь)) (сертификат Ь здесь не зависит от а), Таким образом, Х Е,ИР. Теорема доказана. 4.6. Теорема Кука Определение. Язык 1, (задача распознавания) называется Ь?Р-трудным, если любой язык Ь1 вз ИР полиномиально сводится к В. В соответствии с теоремой 4.10, если язык Ь является ?ч Р-трудяъпя и 1 Е Р, то ИР С Р и, с учетом теоремы 4.11, Р = ИР. И обратно, если Р ф ИР, то В ф Р. Таким образом, ПР трудность язьпса явпяется косвенным свидетельством того, что В ф Р (косвенным потому, что вероятно Р зЬ МР, но это пока не доказано и не опровергнуто) . Определение. Язык В (задача распознавания) называется ФР-полным, если В б 1у Р и Ь явпяется 1у Р-трудным.

Естественно возникает вопрос о том, существуют яи такие "универсапьные" задачи в классе 1У Р, к которым попиномиапьно сводятся все задачи нз ИР. Оказывается, что существуют. Первый результат такого рода бып установлен С. Кухом [12). Теорема 4.12 (С. Кук). Задача ВЫП (о выполнимоспзп КНФ) являетпся 1У Р-полной. Лоназагпвльспзво. Выше уже доказано, что ВЫП б ИР. Поэтому надо доказать, что любой язык б из МР попиномиаяьно сводится к ВЫП. Пусть 1 б МР и В С А'. Это означает, что существуют полипом й(п), алфавит В и предикат С(х, у): А' х В' -+ 1 "истина", "ложь") такие, что фя, у) б Р н дпя любого слова а б А' справедливо а б В в=э ЗЬ(/Ь|, < д(!а/)ЙЯ(а, Ь)).

Нам надо показать, что б попиномиадьно сводится к ВЫН. Это означает, что надо построить такое преобразование с полиномиапьной сложностью у: А' -+ С', где С вЂ” алфавит задачи ВЫП, что а б В в=э ~в(а) = Рв — выполнимая КНФ от некоторых переменных.

Так как Я(т, у) Е Р, то существует машина Тьюринга М, которая распознает предикат фз, у) за время (чнспо шагов), не превосходящее некоторого попинома рв от длины входа. Будем считать, что начальная конфигурация машины Мь является стандартной, то есть пара (о, Ь) представляется на ленте двумя словами а и Ь с одной разделяющей ячейкой, в которой ставится пустой символ Л, головка обозревает са.- мый левый символ слова а и машина находится в начальном состоянии уь Тогда время работы Мь на произвольной паре (а, Ь) не превышает рв0 а(+ )Ь)+1) .

Будем считать, что машина Мь останавливается только в одном нз двух заключительных состояний, причем заключительное состояние дв машины Мь соответствует ответу "да" (какое состояние соответствует ответу "нет" дпя нас будет не важно). Пусть дано а й А* и ~а~ = и. Тот факт, что а б 1, равносилен в соответствии с (4.2) тому, что найдется слово Ь б В' с длиной )Ь( < о(п) такое, что машина Мп начав работу на паре (а, Ь), прилет в состояние дв = "да". Прн этом время работы Мь на паре (а, Ь) не превосходит рв(п + д(п) + 1) = р(п), где р — некоторый попином.

Отметим, что 50 можно считать, что во всех полиномах все коэффициенты неотрицательны. Тогда р(л) ) и + 1+ 4(п). Несколько модифицируем программу машины Мь А именно, если мальпика М~ находится в некотором заключительном состоянии и головка обозревает некоторый символ, то пусть машина М~ оставляет в ячейке тот же символ, головха никуда не сдвигается и машина остается в том же состоянии. То есть реально ничего не происходит, но формально машина продолжает работать бесконечно.

Полученную машину обозначим М. Тогда для слова а Е А' длины !а! = л имеем: а б В 4=» ЗЬ Е В"(!Ь! ( с(л) и машина М, запущенная на паре (а, Ь), в момент времени р(л) будет находиться в состоянии 4с = "да"). (4.2) Наша дальнейшая пель — записать правую часть в этой равносильности в виде КНФ Гз(вц..., т,„) от некоторых переменных, так чтобы формула Га была выполнима тогда и только тогда, когда эта правая часть истинна.

Перепишем (4.2) более попробно: а Е В с=" ЛЬ Е В ВКо, Кз,, .,, Кр~„д (!Ь! < 4(л) и Кэ, Кц..., Кр~„> — конфигурации машины М такие, что Ке — начальная конфигурация для пары (а, Ь), состояние в Кр~„~ есть се и для каждого 1 = О, 1,..., р(н) — 1 конфигурация К,.~ получается из К. по программе машины М).

(4.3) Пусть ячевки ленты в М занумерованы пелыми числами слева направо и ячейка, с которой головка начинает работать (и с которой начинается слово о), имеет номер О. Тогда за р(л) тактов головка не может попасть в ячейки с номерами меньше — р(п) и больше р(л). Поэтому можно считать, что конфигурации Кш Кь .,,, Кр~„~ определены только на зоне ! — р(п),р(н)! ленты.

Пусть маппша М имеет ленточный алфавит Р = (4 4 И ) где Ые = Л, при этом А С Р и В С Р. Пусть 11' = (дэ,дм ., щ) — множество всех состояний машины М, причем д~ — начальное состояние и ое = "да". Введем булевские переменные х';„.,у!,яь~, где г = -р(п), -р(п) + 1,..., р(л);у = О, 1, ,гл; Ь = О, 1,...,1;г 0,1,...,р(л) и приладим им следующий смысл; я,'; = "истина" с=» в 4-й ячейке в конфигурации К~ находится у,' = "истина" л=» в южфигурапии К» головка обозревает ячейку с номером»; зь — — "истина" л=» в ковфигурапии К» состояние дь.

Искомую формулу Рь мы будем строить как КНФ от всех этих переменных Гь((х,',), (у,'), (зь)) причем так, чтобы она была выполнима тогда и только тогда, когда правая часть в (4.3) истинна. Лля этого достаточно, чтобы КНФ Ре была истинна на некотором наборе тогда и только тогда, когда: 1) этот набор корректно задает набор конфигурапий Кь, Кь Кр»ьг машины М; 2) при этом конфигуация Ко является правильной начальной конфигурацией для пары (а, Ь), где а — заданное слово и Ь б В'— какое-нибудь слово длины не более у(п); 3) в конфигурации Кр»„г состояние йе = "да"; 4) для каждого ) = О, 1,..., р(п) — 1 конфигурация Кгы получается из К по программе машины М.

Рассмотрим свойство 1). Если задана конфигурация К», то по ней однозначно определяются значения переменных х»д, уз я„' при данном й Обратное неверно, поскольку, напри»лер, если сразу 2 переменные х,'.„ и х,'.„ нстинны,то это означает,что в конфигурации К, в ячею»е гд»зг » должны находиться и символ дй и символ д1г Легко понять, что условие корректного задания конфигураций выражается следующим образом: х» гд » зь при каждом 2 для каждого» ровно одна из переменных "истина"; при каждом 2 ровно одна из переменных "истина" и при каждом 2 ровно одна из переменных "истина'. Пусть Н(и»,..., и,) — функция алгебры логики, равная 1 тогда и только тогда, когда среди им..., и, ровно 1 единица. Лемма 4.1б.

Функцию Н(им...,и,) можно предстпавить в виде КНФ с длиной (числом литпералов) не более 52. Доказательство. Легко проверить, что Н(иь, .., и ) = (и» 4 из 'г»... у и )Й(35»р (6 Ч й )). 52 Ллина этой КНФ равна в+ -лз-). 2 = вз. Лемма 4.16. Тоги факт, чтпо набор переменных х,' чу», яь» корректпно задает конфигурации Ко, Кь ..,, Круф можно выразить в виде КНФ Р» длины не Более р»(п), где р2 — некоторый полинам. Ноказатаельсотво. Этот факт выражается формулой а г(») т $ т о Р(») с с 1 "с ~~»=ОН(У-р(») У-р(»)<п ~уз(»)) с от=ОН(звзгн''' ~г()' Представляя каждую функцию Н с помткцью КНФ в соответствии с леммой 4.15, получим КНФ Рт длины (р(п)(2р(п)+1)(та+1) +(р(п)+1)(2р(п)+1) +(р(п)+1)(!+1) < р1(п), где рт (и) — некоторый полинам.