Главная Промышленная автоматика.


Рис. 10.15.

*10.26. Известно, что некоторые частные случаи задачи об изоморфизме графов (например, изоморфизм планарных графов) легкие. Другие столь же трудны, как и общая задача. Покажите, что задача об изоморфизме корневых ориентированных ациклических графов имеет ту же сложность, что и задача об изоморфизме произвольных графов.

*10.27. Контекстным называется язык, допускаемый НМТ с емкостной сложностью «+1 (эта мащина называется линейно ограниченным автоматом: см. Хопкрофт, Ульман [1969]). Покажите, что задача выяснения, допускает ли данный линейно ограниченный автомат данный вход, полна для полиномиальной памяти, т. е. задача принадлежности цепочки произвольному контекстному языку полна для -SPACE.

10.28. Покажите, что задача эквивалентности двух регулярных выражений полна для полиномиальной памяти.

**10.29. Опишите алгоритм, допускающий множество кодов всех регулярных выражений R, представляющих непустое множество, который можно реализовать на ДМТ с линейно ограниченной памятью.

Проблемы для исследования

10.30. Одна из очевидных открытых проблем -- выяснить, выполняются ли равенства 5-TIME=olf5-TIME и olf-TlME= = 5*-SPACE. Если учесть объем работы, проделанный в поисках алгоритмов, решающих NP-полные задачи за полиномиальное время, то похоже, что эта проблема по меньшей мере столь же сложна, как некоторые классические проблемы математики, такие, как гипотеза Ферма ("Имеет ли уравнение x"+«/"=z" решение в целых числах для «>3?") или проблема четырех красок ).

1) В Bull. Атег. Math. Soc, 82, №5 (1976), 711-712, опубликовано сообщение о решении проблемы четырех красок, которое нашли с помощью ЭВМ американские математики Аппель и Хакен: Более подробное изложение их результатов см. в Illinois J. Math., 21, № 3 (1977), 429- 567.- Прим. ред.



10.31. В случае неудачи с 10.30 было бы интересно получить нетривиальный результат, дающий такую функцию Г(п), что всякий язык из oГ5-TIME распознается детерминированной машиной с временной сложностью не более Г (п). Это не показано даже для Т(п)=2».

Замечания по литературе

Дополнительную информацию о недетерминированных машинах Тьюринга можно найти в книге Хопкрофта, Ульмана [1969]. Теорему 10.1, устанавливающую связь между емкостными сложностями детерминированных и недетерминированных машин, доказал Сэвич [1970].

Ключевая теорема о NP-полноте задачи выполнимости принадлежит Куку 119716]. Много классических NP-полных задач привел Карп [1972], ясно продемонстрировав важность понятия NP-полноты. С тех пор к семейству известных NP-полных задач были добавлены новые, найденные Сахни [1972], Сети [1973], Ульманом [1973], Раундзом [1973], Ибаррой, Сахни [1973], Хантом, Розенкранцем [1974], Гэри, Джонсоном, Стокмейером [1974], Бруно, Сети [1974] и многими другими. Интересно, что до Кука в нескольких работах была показана полиномиальная взаимосвязь между некоторыми NP-полными задачами, но объем всего класса не был осознан. Например, Данциг, Блаттнер, Рао [1966] установили связь между задачами о коммивояжере и о кратчайшем пути с неотрицательными весами. Диветти, Грасселли [1968] описали связь между задачами о покрытии множествами и о множестве ребер, разрезающих циклы.

Задачи, полные для -SPACE, впервые рассмотрели Мейер, Стокмейер [1972]. Первый язык, полный для памяти, неявно описал Сэвич [1971], определив язык (множество проходимых лабиринтов), полный для log/i-памяти. Джоунс [1973] и Стокмейер, Мейер [1973] рассмотрели ограниченные формы сводимости задач за полиномиальное время. Бук [1972, 1974] доказал несравнимость некоторых классов сложности.

Упр. 10.8 и 10.9 взяты у Кука [19716], упр. 10.10 и 10.12 - у Карпа [1972], упр. 10.13 - у Стокмейера, Мейера [1973] и Ханта [1973а], упр. 10.14 и 10.28- у Стокмейера, Мейера [1973], а упр. 10.15-10.18 - у Гэри, Джонсона, Стокмейера [1974]; рис. 10.14 представляет собой улучшенный вариант, предложенный Фишером. Доказательство NP-полноты задачи 3-раскрашиваемости планарных графов появилось в работе Стокмейера [1973]. Упр. 10.20 заимствовано из работы Ивена [1973], упр. 10.21 - Ульмана [1973], упр. 10.25 - Кука [19716], а редукция, нужная для решения упр. 10.27, взята у Карпа [1972]. Доказательство теоремы 10.13 предложил нам Ивен.



НЕКОТОРЫЕ ДОКАЗУЕМО ТРУДНО РАЗРЕШИМЫЕ ЗАДАЧИ

в этой главе мы приводим доказательства того, что для двух классов расширенных регулярных выражений задача пустоты дополнения трудно разрешима, т. е. любой алгоритм, решающий ее для любого из двух классов, тратит по меньшей мере экспоненциальное время. Для одного из этих классов устанавливается нижняя оценка, существенно превышающая экспоненту. В частности, будет показано, что эта задача требует времени, большего чем

для любой конечной башни из двоек. Прежде чем устанавливать нижние оценки, мы рассмотрим результаты о иерархиях, показывающие, что "чем больше времени или памяти можно использовать для вычислений, тем больше языков можно распознать".

11.1. ИЕРАРХИИ ПО СЛОЖНОСТИ

В гл. 10 мы видели, что некоторые задачи полны для недетерминированного полиномиального времени или же для полиномиальной памяти. Чтобы доказать полноту конкретных задач, мы показывали, как в терминах данной конкретной задачи представляется произвольная задача из класса сАГ-ТШЕ или -SPACE.

Техника доказательств представляла собой, по существу, технику моделирования. Например, мы показали, что задача выполнимости булевых формул NP-полна, а задача пустоты дополнения для регулярных выражений полна для полиномиальной памяти, причем в обоих случаях результат получался прямым вложением вычислений на машинах Тьюринга в частные случаи этих задач. Полноту других задач мы показали, сводя к ним какую-нибудь задачу, о которой уже известно, что она полна для соответствующего класса задач. Таким образом, мы показали, что оба класса оЛГ5*-Т1МЕ и -SPACE





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 [146] 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.0037