Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 98
Текст из файла (страница 98)
все, что с помощью НМТ делается за полиномиальное время, ДМТ в действительности также может выполнить за полиномиальное время (которое, возможно, выражается полиномом более высокой степени). 10.1.4. Пример из Л~Р: проблема коммивояжера Для того чтобы осознать, насколько обширен класс Л'Р, рассмотрим пример проблемы, которая принадлежит классу ЛР, но, предположительно, не принадлежит Р, — пробзему колсииволжера (ПКОМ). Вход ПКОМ (как и у ОДМВ) — зто граф, каждое ребро которого имеет целочисленный вес (рис.
10.1), а также предельный вес и'. Вопрос состоит в том, есть ли в данном графе "гамильтонов цикл" с общим весом, не превышающим 1г'. Ганиль- 10.1. КЛАССЫ Р И ХР 429 шопов цикл — это множество ребер, соединяющих узлы в один цикл, причем каждый узел встречается в нем только один раз. Заметим, что число ребер в гамильтоновом цикле должно равняться числу узлов графа. Одна из версий недетерминированной допустимости Заметим, что мы требовали останова нашей НМТ за полиномиальное время на любой из ветвей (ее работы), независимо от того, допускает она или нет. Можно было бы также установить полиномиальное ограничение во времени Т(п) лишь для тех ветвей, которые ведут к допусканию, т.е.
определить ЛГР как класс языков, допускаемых НМТ, которые допускают с помощью хотя бы одной последовательности переходов длиной не более Т(п), где Т(п) — некоторый полипом. Однако в результате мы получили бы тот же самый класс языков, и вот почему.
Если нам известно, что М, если вообще допускает, делает это в результате 7(п) переходов, то ее можно модифицировать так, чтобы на отдельной дорожке ленты она вела счет до Т(п) и останавливалась, не допуская, если счет превысит Т(п). Число шагов модифицированной М могло бы достигать 0(Т'(п)). Но если Т(п) — полипом, то и 7"(п)— полипом. В действительности, класс Р можно было бы также определить с помощью машин Тьюринга, допускающих за время Т(п), где Т(п) есть некоторый полипом. Эти МТ могли бы не останавливаться, не допуская.
Но с помощью такой же конструкции, как и для НМТ, мы могли бы модифицировать ДМТ так, чтобы она считала до 71п) и останавливалась, перейдя эту границу. Время работы такой ДМТ было бы 0(Тз(п)). Пример 10.3. Граф, изображенный на рис. 10.1, имеет в действительности лишь один гамильтонов цикл — (1, 2, 4, 3, 1). Его общий вес составляет 15 ь 20+ 18+ 1О = 63. Таким образом, если И' имеет значение 63 или больше, то ответ — "да", а если И'< 63, то ответ — "нет". Однако простота ПКОМ для графа с четырьмя узлами обманчива.
В данном графе попросту не может быть более двух различных гамильтоновых циклов, учитывая, что один и тот же цикл может иметь начало в разных узлах и два направления обхода. Но в графе с е узлами число различных циклов достигает 0(гп!), факториала числа пь что превышает 2' для любой константы с. П Оказывается, что любой способ решения ПКОМ включает перебор, по сути, всех циклов и подсчет общего веса каждого из них. Можно поступить умнее, отбросив некоторые, очевидно неподходяшие, варианты. Однако, по всей видимости, при любых на- ших усилиях все равно придется рассматривать экспоненциальное число циклов перед тем, как убедиться в том, что ни один из них не имеет вес меньше предельного 1г', или отыскать такой цикл.
430 ГЛАВА 10. ТРУДНОРЕШАЕМЫЕ ПРОБЛЕМЫ С другой стороны, если бы у нас был недетерминированный компьютер, то можно было бы "угадать" перестановку узлов и вычислить общий вес цикла, образованного узлами в этом порядке. Если бы существовал реальный недетерминированный компьютер, то при обработке входа длины и ни на одной из ветвей ему не пришлось бы сделать более О(п) шагов.
На многоленточной НМТ перестановку можно угадать за О(п ) шагов, и столько же времени понадобится для проверки ее общего веса. Таким образом, одноленточная НМТ может решить ПКОМ за время, не превышающее Огп ). Делаем вывод, что ПКОМ принадлежит классу Л7э. 10.1.5. Полиномиальные сведения Экземпляр гг Экземпляр Р, да нет Рис. 10.2. Повторение картины сведения Допустим, что мы хотим доказать утверждение: "если Р, принадлежит Р, то и Р, принадлежит гг'. Поскольку мы утверждаем, что Р, не принадлежит Р, можно будет утверждать, что и Рг не принадлежит 7э. Однако одного лишь существования алгоритма, обозначенного на рис.
10.2 как "Построение", не достаточно для доказательства нужного нам утверждения. В самом деле, пусть по входному экземпляру проблемы Рг длиной ш алгоритм вырабатывает выходную цепочку длины 2, которая подается на вход гипотетическому алгоритму, решающему Рг за полиномиальное время. Если решающий Рг алгоритм делает это„скажем, за время 01по), то вход длиной 2" он обработает за время 0(2 ), экспоненциальное по т.
Таким образом, алгоритм, решающий Рп обрабатывает вход длиной ш за Это утвержденна не совсем верно. В действительности мы лишь предполагаем, что Р, не принадлежит Р, на том весьма веском основании, что Р, является гЧР-полной" 1понятне "1чр- полноты" обсужлается в разделе 10.1.6). Затем мы доказываем, что Р, также является ' гЧР-полной" н, таким образом, не принадлежит Р на том же основании, что н Ра 431 10.1. КЛАССЫ Р И гчР Основной метод доказательства того, что проблему Рг нелшя решить за полиномиальное время (т.е.
Р, не принадлежит Р), состоит в сведении к ней проблемы Р„относительно которой известно, что она не принадлежит Р. Данный подход был представлен г на рис. 8. 7, который воспроизводится здесь в виде рис. ! 0.2. время, экспоненциальное по т. Зги факты целиком согласуются с ситуацией, когда Рз приналлежит Р, а Р~ — нет.
Даже если алгоритм, переводящий экземпляр Р~ в экземпляр Рп всегда вырабатывает экземпляр, длина которого полиномиальна относительно длины входа, то мы все равно можем не добиться желаемого результата. Предположим, что построенный экземпляр Р, имеет ту же длину яз, что и Рь но сам алгоритм преобразования занимает время, экспоненциальное по е, скажем, 0(2 ). Тогда из того, что алгоритм решения Р, тратит на обработку входа длиной л время 0(н~), следует лишь то, что существует алгоритм решения Р„которому для обработки входа длиной е нужно время О(2 -ь т ). В этой оценке времени работы учитывается тот факт, что необходимо не только решить итоговый экземпляр Р„но и получить его.
И вновь возможно, что Рз принадлежит Р, а Р, — нет. Правильное ограничение, которое необходимо наложить на преобразование Рз в Рп состоит в том, что время его выполнения должно полиномиально зависеть от размера входных данных. Отметим, что если при входе длины а преобразование занимает время О(яг), то длина выходного экземпляра Рз не может превышать числа совершенных шагов, т.е. она не больше слг', где с — некоторая константа.
Теперь можно доказать, что если Р, принадлежит Р, то и Р, принадлежит Р. Для доказательства предположим, что принадлежность цепочки длины н к Р, можно выяснить за время 01п ). Тогда вопрос о принадлежности Р, цепочки длины т можно решить за время О(яг' + (слг)"); слагаемое яг' учитывает время преобразования, а (ст')"— время выяснения, является ли результат экземпляром Р,. Упрощая выражение, видим, что Р, может быть решена за время 0(е' + сгл ). Поскольку с, 1 и Š— константы, это время зависит от е полиномиально, и, следовательно, Р~ принадлежит Р.
Итак, в теории труднорешаемости используются только нолиномиальлые сведения (сведения за полиломиальное врсия). Сведение Рз к Рз является полиномиальным, если оно занимает время, полиномиальное по длине входного экземпляра Рз. Как следствие, длина выходного экземпляра Рз будет полиномиальной по длине экземпляра Рь 10.1.6. МР-полмые проблемы Теперь познакомимся с группой проблем, которые являются наиболее известными кандидатами на то, чтобы принадлежать МР, но не принадлежать Р. Пусть Š— язык (проблема) из класса ЛЕР. Говорят, что Е является УР-полным, если для него справедли- вы следующие утверждения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
