1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 85
Текст из файла (страница 85)
(Клика) Содержит ли данный неориентированный граф йклику? 3. 1'Узельное покрьипие) Имеет ли данный неорнентированный граф узельное покрытие размера й? 4. (Гамилыгюнов цикл) Имеет ли данный неориентированный граф гамильтонов цикл? б. (Раскрашиваемость) Является ли данный неориентированный граф Ьраскрашиваемым? б. (Множество узлов, разрезающих циклы) Имеет ли данный ориентированный граф й-элементное множество узлов, разрезающих циклы? 7. (Множество ребер, разрезающих циклы) Имеет ли данный ориентированный граф Й-элементное множество ребер, разрезающих циклы? 8. (Ориентированный гамильтонов цикл) Имеет ли данный ориентированный граф ориентированный гамильтонов цикл? 9.
(Покрытие множествами) Существует ли для данного семей- лат Гл. 10. ИР-палима зАдАчи ства множеств Ям Я„..., Я„х) такое подсемейство из й множеств Я„, 5„,..., Я,а, что а а 0 З~ = 0 Зу? 10. (Точное попрытпие) Существует ли для данного семейства множеств Я„Я„..., З„подсемейство попарно непересекающихся множеств, являющееся покрытием? Д о к а з а т е л ь с та о. Принадлежность задач 1 и 2 классу Д'У показана соответственно в примерах 10.4 и 10.3. Аналогично для каждой из остальных задач надо построить недетерминираванную машину Тьюринга (или, если читателю угодно, недетерминкраванную РАМ) полинамиальной сложности, которая "угадывает" решение и проверяет, что это действительно решение.
Детали оставляем в качестве упражнения. Д Докажем, что всякий язык из Д'У палиномиально трансформируем в задачу выполнимости; тем самым будет установлено, что задача выполнимости булевых формул )т)Р-полна. Теорема 10.3. Задача выполнимости булевой формулы ЫР-полна. Д о к а з а т е л ь с т в о. Мы уже знаем, что задача выполнимости принадлежит 4'бх. Острлось показать, что всякий язык 1. из Д'У палиномиально трансформируем в задачу выполнимости. Пусть М вЂ” недетерминнроваиная машина Тьюринга, распознающая 1. за полиномиальное время, и пусть на ее вход подана цепочка то.
Из М и гв можно построить булеву формулу тоэ, выполнимую тогда и только тогда, когда М допускает го. Основная трудность доказательства — показать, чта для каждой машины М найдется алгоритм, который построит булеву формулу гвэ из го за время, ограниченное полиномом. Этот полинам зависит от М. В силу леммы 10.1 каждый язык из е1РУ распознается недетерминированной одналенточной машиной Тьюринга за полиномиальиое время.
Поэтому можно считать, что М имеет всего одну ленту. Пусть состояниями М будут о„о„..., ою а символами иа ленте— Х„Х„..., Х„, Пусть р(п) — временная сложность машины М. Предпаложйм, что цепочка тв, поданная на вход машины М, имеет длину и. Таким образом, если М допускает го, то делает это не более чем за р(п) шагов. Если М допускает го, то найдется хотя бы одно такая последовательность МО Яэ, Яы..., (сч, что Яа— начальное МО, Я~ х )- Я, для 1«-1(д, Яе — допускающее МО, д(р(п) и ни одно МО не занимает более р(п) клеток на ленте. ') Коиечиые множества мы кодируем цепочками вида (1„Ге...., Гм), где ту — десятичные (или двоичные) целые числа, представлякхцие ваемеяты этих множеств.
Если во всех миожествах всего л раэиых элементов, мы представляем рй влемеит целым числом й 10.4. НР-полнотА ЗАдлчи Выполнимости Построим булеву формулу 1в„которая "моделирует" последовательность МО, проходимых машиной М. Любое присвоение значений истина (число 1) и ложь (число 0) переменным формулы п1а соответствует самое большее одной последовательности МО, возможно незаконной (т. е. такой, которая не может на самом деле реализо- ватьсЯ). БУлева фоРМУла п1а пРимет значение 1 тогда и только тогда, когда это присваиванне значений переменным соответствует последовательности МО Щ, Яи..., ()а, ведущей к допусканию входа.
Иными словами, булеза формула п1, будет выполнима тогда и только тогда, хагда М допускает п1, В качестве пропозициональных переменных в гва употребляются следующие переменные. Перечислим их вместе с их подразумеваемой интерпретацией. 1. С<1, 1, !>=1 тогда и только тогда, когда 1-я клетка на входной ленте машины М содержит символ Ху в момент времени й Здесь 1<1<р(и), 1<1<т и 0<!(р(и). 2. 5<й, !>=1 тогда и только тогда, когда М в момент времени ! находится в состоянии и . Здесь 1<й =з и 0 =!<р(и).
3. гт'<1, !>=1 тогда и только тогда, иогда головка в момент времени ! обозревает 1-ю клетку. Здесь 1<1<р(и) и 0<!< <р (и). Таким образом, пропозициональных переменных всего 0(р'(и)) и их можно представить двоичными числами, содержащими не более с 1оя и разрядов, где с — постоянная, зависящая от р. В дальнейшем удобно будет представлять себе пропозициональную переменную как один символ, а ие с 1од и символов.
Зта потеря множителя с!ад и не может отразиться на полиномиальной ограниченности времени, затрачиваемого на вычисление той или иной функции. Из этих пропозициональных переменных построим булеву формулу п1„следуя структуре последовательности МО Я„Я„...,(,1 . В этом построении мы воспользуемся предикатом У(х„х„...,х„), принимаихцим значение 1, когда в точности один из аргументов х„х„..., х„принимает значение 1. Предикат У можно выразить булевой формулой вида () (х„хю ..., ха) = (~, + х, +... + хг) ( Ц (, + ) . (10.1) 1. / ! Первый множитель в (1О.!) утверждает, что по нрайней мере одна из переменных х, истинна.
Остальные г(г — 1)/2 множителей утверждают, что никакие две переменные не являются истинными одновременно. Заметим, что формальная запись формулы (1(хь х„..., х,) имеет длину 0(г')'), ') Напомним, что мы считаем переменную одним символом. Строго говоря, потребуется 0(га!ояг) а, значит, ие более 0(га) символов. ч13 Гл. пх нР-полныа зАдАчи Если М допускает ш, то найдется допускающая последовательность МО Я„ Яо..., О,, проходимая машиной М в процессе обработки цепочки ~о. Для упрощения рассмотрений мы, не умаляя общности, будем считать, что машина М модифицирована так, что она делает ровно р (и) шагов, а все ее МО содержат р (и) клеток.
Этого можно добиться, заставив М, если нужно, работать после перехода в допускающее состояние, но не изменяя его и ие сдвигая головку, и дополнив все МО нужным числом пустых символов. Поэтому будем строить в, как произведение семи формул А, В,..., О, которые утверждают, что 0„0о..., 0~ — допускающая последовательность МО, причем каждое МО Щ имеет длину р(п) и д=р(п).
Утверждение о том, что 9„Яо..., Яры, — допускающая последовательность МО, равносильно совокупности утверждений: 1) в каждом МО головка обозревает ровно одну клетку; 2) в каждом МО в каждой клетке ленты стоит ровно один символ; 3) каждое МО содержит в точности одно состояние; 4) при переходе от одного МО к следующему изменяется содержимое разве что клетки, обозреваемой головкой; 5) изменение состояния, положения головки и содержимого клетки при переходе ат МО к следующему происходит в соответствии с функцией переходов машины М; 6) первое МО является начальным; 7) состояние в последнем МΠ— заключительное. Построим булевы формулы А, ..., О, соответствующие утверждениям 1 — 7.
1. А утверждает, что в каждый момент времени машина А( обозревает в точности одну клетку. Пусть А, утверждает, что в момент (обозревается в точности одна клетка. Тогда А=А, А,, А,„„ где А =(7(В», 1>, В<2, г>, ..., В<р(п), 1>). Заметим, что если раскрыть выражение, обозначенное через У, то окажется, что формула А имеет длину 0(р' (а)) и ее можно записать за такое же время. 2. В утверждает, что каждая клетка ленты в каждый момент времени содержит в точности один символ. Пусть Вн утверждает, что 1-я клетка ленты в момент времени (содержит равно один символ. Тогда В=ЦВ,, сс где Вм — — У (С<1, 1, 1>, С <1, 2, 1>,..., С<1, и, 8>).
Длина каждой формулы Вн не зависит от и, поскольку размер и ленточного алфавита зависит только от машины Тьюринга М, Таким образом, В имеет длину 0(р'(и)). со.а. ио.полнотл злдлчи выполнимости 3. С утверждает, что в каждый момент времени 1 машина М находится в одном и только одном состоянии: С= Ц и(В<1, 1>, В<2, 1>, ..., В<з, 1>).
о<схасас Так как число состояний з машины М постоянно, то С имеет длину 0(р (а)). 4. Р утверждает, что в любой момент времени 1 можно изменить содержимое не более чем одной клетки '): Р= Д [(С«, !, 1> С«, 1,1+1>)+Н<, 1>). с, с, с Формула (С<с', 1, 1>=С<с, 1, 1+1>)+Н<с, 1> утверждает, что либо (а) в момент 1 головка обозревает клетку 1, либо (б) 1-й символ записан в клетке 1 в момент 1+1 тогда и только тогда, когда он был записан там в момент 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
