(см. сложность) Элементы теории сложности алгоритмов и вычислений. Хахаян (2010) (1186152), страница 12
Текст из файла (страница 12)
В нашем примередизъюнкция будет выполнена относительно t, еслиодновременно не окажется, что t(ui)~F, t ( n 3)-T, t{us)~F.Набор С дизъюнкций над U .называется выполнимым в том итолько, в том случае, если найдется некоторый наборзначений истинности на множестве U такой, чтоодновременно выполнены все Дизъюнкции из С. Такой наборзначений истинности называется выполняющим наборомзначений истинности для С.
Задача. ВЫПОЛНИМОСТЬформулируется следующим образом:ВЫПОЛНИМОСТЬУСЛОВИЕ. Заданы множество переменных U и набор С дизъюнкций над U.ВОПРОС. Существует ли выполняющий набор значенийистинности для С?Например, пусть U = {и1; и2} и С= {{ us, а 2}, { a hи2}}. Это индивидуальная задача из ВЫП, ответ на которуюесть «да». Выполняющее задание значений истинностиопределяется так: t(ui) = t(u2) = Т. С другой стороны, заменивС на С' ={{ и/, u2},{uh и2},\ш 2}}, получим примериндивидуальной задачи, ответ на которую есть «нет»,поскольку С невыполнима. Теперь можно сформулироватьфундаментальную теорему Кука.Теорема 4.4 (теорема Кука). Задача ВЫПОЛНИМОСТЬесть NP-полная задачаДоказательство. Легко видеть, что ВЫП лежит в классеNP.
Недетерминированному алгоритму для ее решениядостаточно указать набор значений истинности на исходноммножестве переменных и осуществить проверку того, что этотнабор значений выполняет все дизъюнкции из исходногонабора С. Все это легко сделать (недетерминированнымобразом) за полиномиальное время. Таким образом, первоетребование, которому должны удовлетворять NP-полныезадачи, выполнено.Для того чтобы проверить выполнение второготребования, вернемся к уровню языков, т.
е. к представлениюВЫП языком Ьвьт = 1[ВЫП, е] для некоторой разумной схемыкодирования е. Необходимо показать, что для всех языков L еNP имеет место соотношение L^Lgun. Разные языки из NPмогут сильно отличаться; число этих языков бесконечно,поэтому невозможно указать отдельное сведение для каждогоиз них. Однако каждый язык из NP может быть представлен встандартном виде, а именно НДМТ-программой, работающейполиномиальное время и распознающей этот язык.Такое представление позволяет иметь дело с общейНДМТ-программой, время работы которой полиномиально, иполучить общую сводимость языка, распознаваемого этойпрограммой, к Ьвьт.
Если эту общую сводимостьспециализировать для конкретной НДМТ-программы М,распознающей LM, то получится искомое полиномиальноесведение Ьм к Ьвып. Таким образом, по существу, для всех ТеNP будет представлено общее доказательство того, чтоL e x LehlВначале рассмотрим произвольную НДМТ-программу Мс полиномиальным временем работы, которая имееткомпоненты Г, 27, b, Q, q0 , qy, q^.S и распознает язык L = LM.Кроме того, пусть р(п) - полином с целыми коэффициентами,ограничивающий сверху временную сложность Т^п). Неумаляя общности, можно считать, что р(п) > п для всех пе Z+.Функция fi, реализующая общую сводимость, будет описана втерминах М, Г, 27, b, Q, q0, qy, qti, <5и р.Удобно рассматривать f L как отображение из множестваслов в алфавите 27 в индивидуальные задачи из ВЫП, а не вслова в алфавите 27, которые кодируют задачи из ВЫП, так какдетали, связанные с кодированием, могут быть легко восполнены.
Таким образом, функция^, будет обладать тем свойством, что для всех хе 27* принадлежность хе L имеет место втом и только в том случае, если для набора дизъюнкций fiix)имеется выполняющий набор значений истинности. Ключом кпостроению функции f L является использование некоторогонабора дизъюнкций для записи утверждения, что хпринимается НДМТ-программой М, т. е. утверждение хе L.Если входное слово хе 27* принимается программой М,то для х существует принимающее вычисление программы М,такое, что число шагов на стадии проверки и число символов вслове-догадке ограничены величиной р(п), где и=|х|.
В такомвычислении будут участвовать лишь ячейки с номерами от р(п) до р(п)+1. Это следует из того, что читающая/пишущаяголовка начинает работу в ячейке с номером 1 и на каждомшаге сдвигается не более чем на 1 ячейку. Проверяющеевычисление полностью определяется заданием в каждый момент времени содержания ячеек с указанными номерами, внутреннего состояния и положения читающей/пишущейголовки. Далее, поскольку в проверяющем вычисленииимеется не более р(п) шагов, то необходимо учесть не болеер{п)+\ моментов времени. Это позволяет полностью описатьтакое вычисление, используя полиномиально ограниченноечисло булевских переменных и некоторый набор значенийистинности на их множестве.Множество переменных U, участвующих в описаниифункции fi, предназначено именно для указанных целей.Перенумеруем элементы множеств Q и Г следующим образом:Q: до, qi = qy, 42=qN, чз,q» где г=|£?1;Г: so = ь,s2, ..., sv,где v=[/"|-l.
В дальнейших рассуждениях будут участвоватьтри типа переменных, каждому из которых придается определенный смысл согласно рис. 4.2. При этом фраза «в моментвремени /» служит сокращением точного выражения «послевыполнения z'-ro шага, проверяющего вычисления».Вычисление программы М очевидным образоминдуцирует на множестве этих переменных набор значенийистинности, если принять соглашение, что при окончаниивычисления раньше момента времени р(п) конфигурацияостается неизменной во все моменты времени послеостановки, т.
е. сохраняются заключительное состояние,положение головки и запись на ленте.В нулевой момент времени запись на ленте состоитиз входного слова х, расположенного в ячейках с номерами от1 до п, и слова-до гадки w в ячейках с номерами от - 1 до \w\,при этом все остальные ячейки пусты. С другой стороны,произвольный набор значений истинности этих переменныхПеременнаяПределы измененияиндексовПридаваемый смысл0 t < р («)0ни, пS/, fcj- р («X Jо{п)</>(«) +—р ( « Х .
К р («} +11В момент времени 1 программа Мнаходятся в срстрянив faВ момент времени / читающая/пяшущая головка просматривает ячейкус номером jВ момент времени i в /• й ячейкезаписан символРис. 4.2 Переменные набора дизъюнкцийfi(x) и придаваемый имсмысл.не обязательно соответствует какому-то вычислению, а темболее принимающему. При произвольном наборе значенийистинности переменных в некоторой ячейке могли бы бытьодновременно записаны несколько различных символов,машина могла бы находиться одновременно в несколькихразличных состояниях, а читающая/пищущая головка моглабы одновременно просматривать любое подмножество ячеек сномерами от -р (п ) до р (п )+ 1. Описание функции fa осуществляется посредством построения такого набора дизъюнкций,содержащего перечисленные переменные, что набор значенийистинности будет выполняющим тогда и только тогда, когдаэтот набор значений истинности индуцируется некоторымпринимающим вычислением на входе х, причем стадияпроверки этого вычисления выполняется не более чем за р(п )шагов и слово-догадка имеет длину не более р(п).
Такимобразом, мы получим импликации: х е L она входе хсуществует принимающее вычисление программы М <=> навходе х существует принимающее вычисление программы М,число шагов которого не превосходит р (п ), а слово-догадка wимеет длину, равную р(п) »существует выполняющеезадание значений, истинности для набора дизъюнкций задачи//.(*)•Это будет означать, что для f L выполнено одно из двухусловий, требующихся в определении полиномиальнойсводимости.
Другое условие, заключающееся в том, что f Lдолжна быть вычислима за полиномиальное время, можнобудет легко проверить после того, как описание f L будетзакончено.Дизъюнкции индивидуальной задачи f L(x) можноподразделить на 6 групп, каждая из которых будет налагатьограничение определенного типа на любой выполняющийнабор значений истинности. Эти группы показаны на рис. 4.3.Легко видеть, что если все 6 групп дизъюнкций действительно осуществляют поставленные перед ними цели, товыполняющийнаборзначенийистинностиобязансоответствовать нужному принимающему вычислению навходе х.
Единственное, что остается - это указать способпостроения групп дизъюнкций, осуществляющих эти цели.Группа G] состоит, из следующих дизъюнкций:i Q [ i .МО0 1 ,;Q%ШТ1 ) .....................Q [ / ,).0 «Крr j ) ,М0,<0(«</ ?К«?;<*Первые р(п)+ 1 из этих дизъюнкций могут бытьвыполнены одновременно в том и только в том случае, если вкаждый момент времени / программа М находится по крайнеймере в одном состоянии. Остальные (р(п)+\)(г+1){г/2)дизъюнкций могут быть выполнены одновременно в том итолько в том случае, если ни в один момент времени /программа М не находится более чем в одном состоянии.Таким образом, Gt выполняет свое назначение.ГруппаДИЗЪЮНКЦИЙQtСаОгGjвj0}Излагаемое ограничениеВ любой -момент времени I программе Af находится ровнов одном состоянии.В любой момент времени i чнтаютая/пишущая головка врос*матрнвает ровно одну ячейку,В любой момент времени I каждая ячейка содержит ровноодни символ из Г.В момент времени 0 вычисление находится в исходной кояфигурации стадии проверки при входе, х,Не позднее чем через р (п) шагов М переходит в состояниеQy и, следовательно, принимает х.Для любого момента времени I, 0 < / < р («), конфигурацияпрограммы М в момент времени / + I получается из конфигураций в момент времени / одноразовым применением функции перехода 6 ,Рис.
4.3 Группы дизъюнкций для /},(х) и ограничения, накладываемыеими на выполняющий набор истинностных значенийГруппы G2 и Gj строятся аналогично, а группы G4 и G,очень просты, каждая из них включает дизъюнкции,состоящие только из одного литерала. На рис.4.4 дано полноеописание первых пяти групп дизъюнкций. Отметим, что какчисло дизъюнкций в этих группах, так и максимальное числолитералов, входящих в каждую дизъюнкцию, ограниченынекоторым полиномом от п (так как г и v - константы, которыеопределяются по Ми, значит, по языку L).Несколько сложнее выглядит описание последней группыдизъюнкций Gfi, которая гарантирует, что каждая следующаяконфигурация машины получается из предыдущей врезультате применения одной команды программы М Этагруппа состоит из двух подгрупп дизъюнкций.Груп п адизъюнкДизъю нкции, входящие в гр уп п уцийо,0*0г0<О* ■(QV, 01- <3(1.1)......
Q-MK 0 < /< р (я ),Ш П1оо[ни, - 1>т и и, ~~р (п) + 1 }...... Я[*.Д («) + !]). 0 < /< p (ii);[// [/, /), ТЩ7\Ь о <р (»), -- P {«}</</"< P («) + >{S[t, 1, 4 S[f. /, 1 ), ....v}), 0 < i < p (rt),- p { n ) <j < p {a) + l,( s iu * i.Ж Ш пы к р т , -pfeK K uW +i,0 <* < *'<a,{Q{M]1, W [0,1}|, {S [0, 0, 0]},{S[0 ,Щ 0, 2, Ш{5[0, п, kS,{SfO, n + l , 0]}, {S[0, й + 2, 0Ц,..... {SfO, p («) + !, Oil,да x ^ s k ski ... «*в>Ю(Р(Л), Ш-Рис. 4.4 Первые 5 групп дизъюнкций дляУДх)Перваяподгруппагарантирует,чтоесличитающая/пишущая головка в момент времени i непросматривает ячейку с номером у, то символ в ячейке сномером у от момента времени i к моменту времени / + 1 неизменится.
Дизъюнкции этой подгруппы имеют вид:{S[i, /,1], H [(t П, 5 [ / + 1, /, Щ, 0 < /< /» (« ).. — jp-foX/</>'{») + 1 ,0 < 1<».Зафиксируем произвольно момент времени / , ячейку сномером у и символ s,. Если в момент времени /читающая/пишущая головка не просматривает ячейку сномером у и в этой ячейке в момент времени i записан символу, а в момент времени г+ 1 его там уже нет, то указанная вышедизъюнкция не будет выполнена (в противном случае онабудетвыполнена).Такимобразом,2(p(n)+\f(v+\)дизъюнкций этой группы выполняют свое назначение.Вторая подгруппа дизъюнкций из группы G6 гарантирует,что перестройка одной машинной конфигурации вследующую происходит согласно функции перехода Sпрограммы М.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
