Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 96
Текст из файла (страница 96)
ГЛАВА 9. НЕРАЗРЕШИМОСТЬ 420 9.7. Литература Результат о неразрешимости универсального языка фактически взят из работы Тьюрвига [9], хотя там он выражен в терминах вычислений арифметических функций и осталова, а не в терминах языков и допустимости по заключительному состоянию. Теорема Райса взята из [8]. Неразрешимость проблемы соответствий Поста была доказана в [7], но приведенное здесь доказательство, не вошедшее в печатные работы, принадлежит Р. В. Флойду (К%. Р!оуг)), Неразрешимость ТАГ-систем Поста (определенных в упражнении 9.4.4) доказывается в [6]. Основополагающими работами о неразрешимости вопросов, связанных с контекстно- свободными языками, являются [1] и [5]. Однако неразрешимость неоднозначных КС- грамматик была установлена независимо друг от друга Кантором [2], Флойдом [4], Хомским и Шютценберже [3!.
1. г'. Ваг-Н|11е1, М. Рег)ез, апг! Е. БЬяп)г, "Оп Гоппа! ргорег|1ез о( яшр!е рЬгазе-зггисшге 8гапипагз*', 2 Р!гопегй. БргасЬгик Коттит)го!гоги-7огзс!г. 14 (1961), рр. 143-172. 2. Р.С. Сап|от, "Оп |Ье ашЪ|8ш|у ргоЫеш |п Вас!|из зуа|ешз", .г. АСМ 9:4 (1962), рр. 477-479. 3. Х. СЬопЫсу апд М. Р.
БсЬигкепЬегйег, "ТЬе а!БеЬгак |Ьеогу о( сопгехг-Тгее!апйиайез", Сотршег Рго8гаттт8 апг! Рогта! Буггетз (!963), Ыог|Ь Но!!апд, Агпзгегдаш, рр. 118-161. (Хомский Н., Шютценберже М. Алгебраическая теория контекстно- свободных языков. — Кибернетический сборник, новая серия, вып.
3. — Мз Мир, 1966, С. 195 †2.) 4. К. %. Р!суд, "Оп ашЬ18и[гу |п рЬгазе в|гас|иге 1апйиа8ез", Соттитсацопг о1 йе АСМ 5:1О (1962), рр. 526 — 534. 5. Б. б(пзЬиг8 апг! б. Е. Козе, "Боте гесигяче!у ипзо!чаЫе ргоЫе|па |п АЬООЬ-Шсе 1ап8иайез", Х АСМ10:1 (1963), рр. 29-47.
б. М. Ь. М)па)гу, "Кеси|ыче ипзо!чаЬ|Н|у о( Роз|'з ргоЫе|п о( '|а8' апд о|йег |ор|сз 1п |Ье |Ьеогу о( Типпй шасЬ|пез", Апла!з оГМайетаг1сз 74 3 (! 961), рр. 437 — 455. 7. Е. Роз|, "А чаг|ап| ор а гесигяче1у ипзо!чаЫе ргоЫеш", Ви!!ебп о7'йе АМЯ 52 (1946), рр. 264-268. 8. Н. б, Кке, "С!акаев ор гесигяче!у епишегаЫе зе|в апг! |Ье|г г!ес!яоп ргоЫешв", Тгалзасггонз о7" гйе АМЯ 89 (1953), рр. 25 — 59.
9. А. М. Типпй, "Оп сошрщаЫе пишЬегз чч1|Ь ап арр1ка|юп |о |Ье ЕпгзсЬе!г!ипйзргоЬ- !еп|", Ргос. Т,опйоп Май. Бог|евку 2:42 (! 936), рр. 230 — 265. 9.7. ЛИТЕРАТУРА 421 ГЛАВА 10 Труды орешаемые проблемы Обсуждение вычислимости переносится на уровень ее эффективности или неэффективности. Предметом изучения становятся разрешимые проблемы, и нас интересует, какие из них можно решить на машинах Тьюринга за время, полиномиально зависящее от размера входных данных. Напомним два важных факта из раздела 8.6.3.
° Проблемы, разрешимые за полиномиальное время на обычном компьютере,— это именно те проблемы, которые разрешимы за такое же время с помощью машины Тьюринга. ° Практика показывает, что разделение проблем на разрешимые за полиномиальное время и требующие экспоненциального или большего времени, является фундаментальным Полиномиальное время решения реальных задач, как правило, является приемлемым, тогда как задачи, требующие экспоненциального времени, практически (за приемлемое время) неразрешимы, за исключением небольших экземпляров. В этой главе изучается теория "труднорешаемости", т.е. методы доказательства неразрешимости проблем за полиномиальное время.
Вначале рассматривается конкретный вопрос ввтолиимости булевой формулы, т.е. является ли она истинной для некоторого набора значений ИСТИНА и ЛОЖЬ ее переменных. Эта проблема играет в теории сложности такую же роль, как Л„и ПСП для неразрешимых проблем. Вначале мы докажем "теорему Кука", которая означает, что проблему выполнимости булевых формул нельзя разрешить за полиномиальное время. Затем покажем, как свести эту проблему ко многим другим, доказывая тем самым нх труднорешаемость. При изучении полиномиальной разрешимости проблем изменяется понятие сведения.
Теперь уже недостаточно просто наличия алгоритма, который переводит экземпляры одной проблемы в экземпляры другой. Алгоритм перевода сам по себе должен занимать не больше времени, чем полиномиальное, иначе сведение не позволит сделать вывод, что доказываемая проблема труднорешаема, даже если исходная проблема была таковой. Таким образом, в первом разделе вводится понятие "полиномиальной сводимости" (сводимости за полиномиальное время). Между выводами, которые дают теории неразрешимости и труднорешаемости, существует еще одно принципиальное различие.
Доказательства неразрешимости, приведенные в главе 9, неопровержимы. Они основаны только на определении машины Тьюринга и общих математических принципах. В отличие от них, все приво- димые здесь результаты о труднорешаемости проблем основаны на недоказанном, но безоговорочно принимаемом на веру предположении, которое обычно называется предположением Р в )ч'Р. Итак, предполагается, что класс проблем, разрешимых недетерминированными МТ за полиномиальное время, содержит, по крайней мере, несколько проблем, которые нельзя решить за полиномиальное время детерминированными МТ (даже если для последних допускается более высокая степень полинома). Существуют буквально тысячи проблем, принадлежность которых данной категории практически не вызывает сомнений, поскольку они легко разрешимы с помощью НМТ с полиномиальным временем, но для их решения не известно ни одной ДМТ (или, что то же самое, компьютерной программы) с полиномиальным временем.
Более того, важным следствием теории труднорешаемости является то, что либо все эти проблемы имеют детерминированные решения с полиномиаяьным временем — решения, ускользавшие от нас в течение целых столетий, либо таких решений не имеет ни одна из них, и они действительно требуют экспоненциального времени. 10.1. Классы Р и ЛРР В этом разделе вводятся основные понятия теории сложности: классы Р и ЛР проблем, разрешимых за полиномиальное время, соответственно, детерминированными и недетерминированными МТ, а также метод полиномиального сведения. Кроме того, определяется понятие "ХР-полноты" — свойства, которым обладают некоторые проблемы из ЛгР. Они, как минимум, так же трудны (в пределах полиномиальной зависимости времени), как любая проблема из класса ЛР.
10.1.1. Проблемы, разрешимые за полиномиальное время Говорят, что машина Тьюринга М имеет временную сложносгпь Т(п) (или "время работы Т(п)"), если, обрабатывая вход и длины п, М делает не более Т(п) переходов и останавливается независимо от того, допущен вход или нет. Это определение применимо к любой функции Т(п), например, Т(п) = 50п' или Т(п) = 3" + 5п'. Нас будет интересовать, главным образом, случай, когда Т(п) является полиномом относительно п. Мы говорим, что язык Т. принадлежит классу Р, если существует полипом Т(п), при котором Т, = ЦМ) для некоторой детерминированной МТ М с временной сложностью Т(п).
10.1.2. Пример: алгоритм Крускала Читатель, вероятно, уже хорошо знаком со многими проблемами, имеющими эффективные решения. Некоторые из ннх, возможно, изучались в курсе по структурам данных и алгоритмам. Как правило, эти проблемы принадлежат классу Р. Рассмотрим одну такую проблему: поиск в графе остовного дерева минимального веса (ОДМВ). ГЛАВА 10. ТРУДНОРЕШАЕМЫЕ ПРОБЛЕМЫ 424 Есть ли что-то между полиномами и экспонентами? В дальнейшем, как и во вступлении, мы часто будем действовать так, как если бы время работы любой программы было либо полиномиальным (О(н") для некоторого целого числа 1), либо экспоненциальным (О(2'") для некоторой константы с> О) илн более того. Известные из практики алгоритмы решения наиболее распространенных проблем, как правило, относятся к одной из этих категорий. Когда мы говорим об экспоненциальном времени, то всегда имеем в виду "время работы, которое больше любого поли- нома".
Однако существуют времена работы программ, лежащие между полиномнальным и экспоненциальным временем. Примером функции, находящейся между полиномами и экспонентами, является функция нье-". Эта функция с ростом и увеличивается быстрее любого полинома, поскольку !оя п в конце концов (при больших и) превосходит любую константу )с. С другой стороны, и'"'" = 2'иеил (если это неочевидно, возьмите логарифм обеих частей). Эта функция растет медленнее, чем 2'" при любой константе с > О, поскольку сн в конце концов превышает (!оя, и)', какой бы малой ни была с. Неформально графы представляются как диаграммы, наподобие изображенной на рис.
10.1. У них есть узлы, которые в данном примере графа пронумерованы 1-4, и ребра, соединяющие некоторые пары узлов. Каждое ребро имеет целочисленный вес. Остовное дерево — это подмножество ребер, с помощью которых соединены все узлы, но циклы отсутствуют, Пример остовного дерева показан на рис. 10.1 — это три ребра, выделенные жирными линиями. Остовное дерево минимального веса — это дерево наименьшего общего веса среди всех остовных деревьев. .Рис. 10 1. Гриф, в котором остовное дерево минимального веса выделено жирными линилмн 10,1. КЛАССЫ Р И МР 425 Для нахождения ОДМВ существует хорошо известный "жадный" алгоритм, который называется ал орингнолг Крускала .
Опишем вкратце его основные идеи. 1 1. Для каждого узла определяется компонент связности„который содержит этот узел и образован с использованием ребер, выбранных до сих пор. Вначале не выбрано ни одно ребро, так что каждый узел образует отдельный компонент связности. 2. Среди еще не выбранных ребер рассмотрим ребро минимального веса, Если оно соединяет два узла, которые в данный момент принадлежат различным компонентам связности, то выполняется следуюшее: а) ребро добавляется в остовное дерево; б) связные компоненты сливаются (объелиняются) путем замены номера ком понента у всех узлов одного из них номером другого.
Если же выбранное ребро соединяет узлы из одного и того же компонента, то это ребро не принадлежит остовному дереву; его добавление привело бы к образованию цикла. Выбор ребер продолжается до тех пор, пока мы не выберем все ребра, или число ребер, выбранных в остовное дерево, не станет на единицу меньше обшего числа узлов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
