1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 90
Текст из файла (страница 90)
Таким образом, регулярное выражение В можно построить за время р'(и), где р' — полипом„растущий по порядку как р'. Более того, В„представляет множество (Д 0 (~е))Р тогда и только тогда, когда х не допускается машиной М. (1 443 ГЛ. Ш, ИР-ПОЛНЫЕ ЗАДАЧИ Итак, в лемме 10.2 построено регулярное выражение над алфавитом Ь 0 (4е), размер которого зависит от М. Мы хотим рассуждать о "языке регулярных выражений, дополнения которых (относительно их алфавитов) представляют иепустые множества".
Так как язык должен определяться над конечным алфавитом, мы будем кодировать регулярное выражение над конечным алфавитом Е следующим образом: 1) +, ', Я, е и скобки обозначают сами себя, 2) 1-й символ алфавита Х (в произвольном порядке) обозначается через 4ети4~, где ш — десятичное представление числа 1. Таким образом, для кодирования любого регулярного выражения над любым алфавитом достаточно 17 символов из алфавита Г=(+, А, Я, е, (, ), 7~, О, 1,..., 9).
Определим язык ).„с:-Г' как множество кодов тех регулярных выражений Я, дополнения которых представляют непустыемножества. Если )г — выражение над алфавитом Х, то дополнение берется относительно Х*. Заметим, что если выражение Я имеет длину п)2, то длина его кода не превосходит За 1оя и. Лемма 10.3. Ь„принадлежит классу У-БРАСЕ. Д о к а з а те л ь с т в о. По теореме 10.1 достаточно построить НМТ М, которая допускает язык Т.„, работая с полииомиально ограниченной памятью.
Пусть)1 — регулярное выражение, код которого подан на вход машины М. В силу теоремы 9.2 по данному регулярному выражению длины и можно построить недетерминированный конечный автомат А с не более чем 2л состояниями, распознающий язык, представленный этим регулярным выражением. НМТ М сначала строит автомат А по коду выражения Я, поданному машине М. Заметим, что по теореме 9.2 можно построить функцию переходов автомата А за время, не превосходящее 0(а'). Допустим, что дополнение множества, представленного выражением Я, непусто.
Тогда существует цепочка х=аи ..а„, не принадлежащая языку, представленному выражением 11. М угадывает ее символ за символом. Для хранения множества 5~ состояний, в которых А может оказаться после прочтения а,...аи 1(1 ..гп, машина М использует массив из 2п битов. Она начинает с множества 5, состояний, достижимых из начального состояния автомата А только с помощью е-переходов.
После того как она угадает а,...а,, автомат А может находиться в одном из состояний множества 5~. Когда М угадывает следующий входной символ а,+„она прежде всего вычисляет Т,+,— — (з"1з'Еб,(з, а,+,) и ЗЕ5;), где 6„— функция переходов автомата А, а затем строит 5„„добавляя к Т,, все состояния из бл(з', е) для з' из Т,+,.
(Обратите внимание на аналогию с злгорйтмом 9.1.) !а.е. 3АдАчи с пОлинОмиАльно ОГРАниченнОЙ пАмятью Когда М угадает а,а,...а, она выяснит, что Б„не содержит заключительного состояния автомата А. Обнаружив это, машина М допускает свой вход, т. е. код регулярного выражения Я. Таким образом, М допускает код выражения Я тогда и только тогда, когда дополнение множества, представленного выражением Я, непусто. П Теперь покажем, что язык Л„, состоящий из кодов тех регулярных выражений, которые представляют множества с непустыми дополнениями, полон для полиномиальной памяти.
Теорема 10.14. Если Е„ допускается ДМТ с временной сложностью Т(п))п, то для каждого Е ЕУ-БРАСЕ найдется такой полипом р„что Е допускаг«)ся за время Т(рс(п)). Д о к а з а тел ь с т в о. Пусть М будет ДМТ, допускающей Е, В силу леммы 10.2 и рассуждений, проведенных выше, существует алгоритм с полиномиально ограниченным временем работы, скажем с временной сложностью р,(п), который по входной цепочке х строит регулярное выражение Я„.
Это выражение в фиксированном 17-символьном алфавите, и, разумеется, оно не длиннее р, ()х(). По лемме 10.2 его дополнение пусто тогда и только тогда, когда хЕЕ. По предположению можно проверить пустоту этого дополнения за Т ()Я„')) =Т(р, ()х))) шагов. Построение Я„занимает р,()х() шагов, а проверка пустоты — Т(р,()х))) шагов. Так как Т (п))л, то для завершения доказательства достаточно взять р (п)=2р,(п)'). П Следствие.
Е, принадлежит У-Т1МЕ тогда и «юлька тогда, когда У-Т 1МЕ = да-БРАСЕ. Д о к а з а т е л ь с т в о. Если Р-Т1МЕ=У-БРАСЕ, то Л„принадлежит У-Т1МЕ по лемме 10.3. Обратное следует из теоремы 10.14 с полиномиальной функцией Т(п). П Теорема 10.15. Если Е„допуская«)ся НМТ свременной сложностью Т(п))п, то для каждого ЕЕУ-БРАСЕ найдется такой полипом р„ипо Е допускается НМТ за время Т(р (и)).
Д о к а з а т е л ь с т в о. Аналогично доказательству теоремы 10.14. П Следствие. Е, принадлежит ))"У-Т1МЕ тогда и толысо тогда, когда е))"У-Т1МЕ=Р-БРАСЕ. 1) В действительности при сделанных предположениях о росте Т мы не можем получить требуемое неравенство т+Т(т)~Т(2т). Для завершения доказательства можно использовать упр. )).9.— Прим. )мд. ГЛ.
!О. НР-ПОЛНЫЕ ЗАДАЧИ упражнения 10.1. Выпишите все правильные последовательности шагов НМТ, изображенной на рис. 10.1, для входа 10101. Допускает ли зта НМТ указанный входу 10.2. Неформально опишите НМТ или недетерминированную программу на Упрощенном Алголе, допускающую (а) множество таких цепочек 10г~10гь ..1О'а, что (,=г, для некоторых 1(гк вь:я, (б) множество таких цепочек хсу, что х и у принадлежат (а, о)е и х — подцепочка в у, (в) множество цепочек, как в (б), но х — подпоследовательность в у. 10.3. Опишите РАМ-программу, моделирующую недетерминированную РАМ-программу.
10.4. Пусть М обозначает (тгсп)-матрицу из нулей и единиц. Напишите программу на Упрощенном Алголе, которая находила бы такую наименьшую (ЗХП)-подматрицу 5 матрицы М, что если М(1, !)=1, то 5(й, !1=1 для некоторого 1(й~з. Какова временная сложность вашей программыр 1О.б. Покажите, что следующие функции конструнруемы по емкости, неформально описав для этого ДМТ, помещавшую маркер в нужную клетку одной из своих лент: (а) и*, (в) 2", (б) пз' па+1 (г) п1. 10.8. Покажите, что если одноленточная НМТ с емкостной сложностью 5(п), имеющая з состояний и 1ленточных символов, допускает слово длины и, то она допускает его не более чем за З5 (п)(зои шагов.
е10,7. Покажите, как вычислить на РАМ значение булевой формулы за время 0(п). 10.8. Покажите, что язык, состоящий из булевых функций, не являющихся тавтологиями '), !х)Р-полон. 10.9. Покажите, что задача об изоморфизме подграфу ("Изоморфен ли данный неориентироваиный граф б некоторому подграфу данного неориентированного графа б'Р") НР-полна.
Указание: Воспользуйтесь ХР-полнотой задачи о клике или о гамильтоиовом цикле. 10.10. Покажите, что задача о ранг(е (ибуществует ли для данной последовательности целых чисел 5=1„г'„..., 1„И целого ') Тознювзгигй называется булеза фориула„принииающая значение 1 на всех наборах значений ее переиенных. УПРАЖНЕНИЯ числа и подпоследовательность в 5, сумма членов которой равна к)") НР-полна. Указание: Используйте задачу о точном покрытии.
*10.11. Покажите, что задача о разбиении (задача о ранце из упр. 10.10 с $ (у=2/г) НР-полна. 1 1 10.12. Покажите, что задача о коммивояжере ("По данному графу 6 с целочисленными весами ребер найти цикл, который включает каждый узел и сумма весов ребер которого не превосходит й") ХР- полна. **10.13. Покажите, что ХР-полна задача распознавания следующего свойства: регулярное выражение без ч (т. е. такое, в котором употребляются только операции + и ) ие представляет всех цепочек некоторой фиксированной длины. Указание: Трансформируйте в эту задачу о регулярных выражениях задачу КНФ-выполнимости. *"10.14.
Покажите, что ХР-полна задача распознавания следующего свойства: регулярное выражение над алфавитом (О) не представляет О*. ""10.15. Пусть О=(У, Е) — неориентированный граф и и„о,— дна различных узла. Разрезом для о1 и п1 называется такое подмножество Яс=Е, что любой путь между о, и и, содержит элемент из 5. Покажите, что НР-полна задача распознавания того, есть ли в графе такой разрез размера й для о, и пм что обе части графа содержат равные количества узлов.
"'*10Л8 Одномерная задача об упаковке состоит в следующем, Пусть 6=(У, Е) — неориентироваиный граф и й — положительное целое число. Существует ли такая нумерация и„о„..., э„узлов из У, что ~1 — 1~<й7 (оеэ )че Покажите, что эта задача ХР-полна. я*10.17. Докажите, что задача о раскраске остается НР-полной, даже если ограничить й числом 3, а наибольшую степень каждой вершины — числом 4. я*10.18. Выполните упр. 10.17 для планарных графов.
Указание: Покажите, что планарный граф на рис. 10.14 можно раскрасить в три цвета только тогда, когда п, и п,' раскрашены одинаково, а также о, и о', раскрашены одинаково. Скомбинируйте этот результат с вашим ответом на упр. 10.17. *10.19. Докажите МР-полноту задачи о клике, непосредственно представляя вычисления НМТ вместо того, чтобы трансформировать ее из З-КНФ-выполнимости. ГЛ.
1О. НР.ПОЛНЫЕ ЗАДАЧИ Рис. 10.14. Планзрныа граф. *10.20. Рассмотрим ориентированный граф с двумя выделенными узлами з н й Припишем каждому ребру целочисленную "пропускную способность". Можно построить максимальный поток из в в Г, многократно находя путь из в в 1 и увеличивая поток вдоль него до максимума, разрешаемого пропускными способностями его ребер.
Покажите, что задача нахождения наименьшего множества путей, на которых следует увеличивать поток, !нР-полна. Указание: Рассмотрите граф типа изображенного на рис. 10.15 и свяжите эту задачу с задачей о ранце. *е10.21. Задача о расписанииработс равными временами вылолнения состоит в следующем. Даны множество работ Я= (У„..., .г'„), лимит времени 1, число процессоров р и частичный порядок < на 5. Существует ли расписание работ из Я, требующее не более 1 единиц времени, т. е. такое отображение 1 из 5 в (1, 2,..., 1), что в каждое целое число отображается не более р работ, и если,1(/', то 1(г)~~(г')1 Покажите, что эта задача г!Р-полна. 10.22.
Покажите, что каждая из задач, перечисленных в теореме !0.2, принадлежит классу Ан'"Р-Т!МЕ. 10.23. Пусть р,(х) и р,(х) — полиномы. Покажите, что некото. рый полипом для каждого х принимает значение, большее р, (р,(х)). 10.24. Выпишите выражение ЕЫАН введенное в доказательстве теоремы 10.3, для 6(дА, х )=((дм Х„Ц, (дм Хь 14)). "*10.25. Постройте алгоритм полиномиальной сложности для проверки 2-выполнимости. Упражнения Е а! — 7 х ! Рве. 10.15.
"10.20. Известно, что некоторые частные случаи задачи об изоморизме графов (например, изоморфизм планарных графов) легкие. ругие столь же трудны, как и общая задача. Покажите, что задача об изоморфизме корневых ориентированных ациклических графов имеет ту же сложность, что и задача об нзоморфизме произвольных графов. "10.27. Контекстным называется язык, допускаемый НМТ с емкостной сложностью н+1 (зта машина называется линейно ограниченным автоматом; см. Хопкрофт, Ульман [1969)). Покажите, что задача выяснения, допускает ли данный линейно ограниченный автомат данный вход, полна для полиномиальной памяти, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
