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