dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 95
Текст из файла (страница 95)
Вначале рассматривается конкретныйвопрос выполнимости булевой формулы, т.е. является ли она истинной для некоторогонабора значений ИСТИНА и ЛОЖЬ ее переменных. Эта проблема играет в теориисложности такую же роль, как Lu и ПСП для неразрешимых проблем. Вначале мы докажем “теорему Кука”, которая означает, что проблему выполнимости булевых формулнельзя разрешить за полиномиальное время. Затем покажем, как свести эту проблему комногим другим, доказывая тем самым их труднорешаемость.При изучении полиномиальной разрешимости проблем изменяется понятие сведения.Теперь уже недостаточно просто наличия алгоритма, который переводит экземпляры одной проблемы в экземпляры другой.
Алгоритм перевода сам по себе должен занимать небольше времени, чем полиномиальное, иначе сведение не позволит сделать вывод, чтодоказываемая проблема труднорешаема, даже если исходная проблема была таковой.Таким образом, в первом разделе вводится понятие “полиномиальной сводимости”(сводимости за полиномиальное время).Между выводами, которые дают теории неразрешимости и труднорешаемости,существует еще одно принципиальное различие. Доказательства неразрешимости,приведенные в главе 9, неопровержимы. Они основаны только на определении машины Тьюринга и общих математических принципах.
В отличие от них, все приво-Стр. 423димые здесь результаты о труднорешаемости проблем основаны на недоказанном,но безоговорочно принимаемом на веру предположении, которое обычно называетсяпредположением P ≠ NP.Итак, предполагается, что класс проблем, разрешимых недетерминированными МТ заполиномиальное время, содержит, по крайней мере, несколько проблем, которые нельзярешить за полиномиальное время детерминированными МТ (даже если для последних допускается более высокая степень полинома). Существуют буквально тысячи проблем, принадлежность которых данной категории практически не вызывает сомнений, посколькуони легко разрешимы с помощью НМТ с полиномиальным временем, но для их решенияне известно ни одной ДМТ (или, что то же самое, компьютерной программы) с полиномиальным временем.
Более того, важным следствием теории труднорешаемости является то,что либо все эти проблемы имеют детерминированные решения с полиномиальным временем — решения, ускользавшие от нас в течение целых столетий, либо таких решений неимеет ни одна из них, и они действительно требуют экспоненциального времени.10.1. Êëàññû P è NPВ этом разделе вводятся основные понятия теории сложности: классы P и NP проблем, разрешимых за полиномиальное время, соответственно, детерминированными инедетерминированными МТ, а также метод полиномиального сведения. Кроме того, определяется понятие “NP-полноты” — свойства, которым обладают некоторые проблемыиз NP.
Они, как минимум, так же трудны (в пределах полиномиальной зависимости времени), как любая проблема из класса NP.10.1.1. Ïðîáëåìû, ðàçðåøèìûå çà ïîëèíîìèàëüíîå âðåìÿГоворят, что машина Тьюринга M имеет временную сложность T(n) (или “время работы T(n)”), если, обрабатывая вход w длины n, M делает не более T(n) переходов и останавливается независимо от того, допущен вход или нет. Это определение применимо клюбой функции T(n), например, T(n) = 50n2 или T(n) = 3n + 5n4. Нас будет интересовать,главным образом, случай, когда T(n) является полиномом относительно n. Мы говорим,что язык L принадлежит классу P, если существует полином T(n), при котором L = L(M)для некоторой детерминированной МТ M с временной сложностью T(n).10.1.2. Ïðèìåð: àëãîðèòì ÊðóñêàëàЧитатель, вероятно, уже хорошо знаком со многими проблемами, имеющими эффективные решения.
Некоторые из них, возможно, изучались в курсе по структурам данныхи алгоритмам. Как правило, эти проблемы принадлежат классу P. Рассмотрим одну такую проблему: поиск в графе остовного дерева минимального веса (ОДМВ).424Стр. 424ÃËÀÂÀ 10. ÒÐÓÄÍÎÐÅØÀÅÌÛÅ ÏÐÎÁËÅÌÛÅñòü ëè ÷òî-òî ìåæäó ïîëèíîìàìè è ýêñïîíåíòàìè?В дальнейшем, как и во вступлении, мы часто будем действовать так, как если бывремя работы любой программы было либо полиномиальным (O(nk) для некоторогоцелого числа k), либо экспоненциальным (O(2cn) для некоторой константы c > 0)или более того.Известные из практики алгоритмы решения наиболее распространенных проблем, какправило, относятся к одной из этих категорий. Когда мы говорим об экспоненциальном времени, то всегда имеем в виду “время работы, которое больше любого полинома”. Однако существуют времена работы программ, лежащие между полиномиальным и экспоненциальным временем.Примером функции, находящейся между полиномами и экспонентами, являетсяфункция nlog n .
Эта функция с ростом n увеличивается быстрее любого полинома, поскольку log n в конце концов (при больших n) превосходит любую константу k. С дру22гой стороны, nlog 2 n = 2(log 2 n ) (если это неочевидно, возьмите логарифм обеих частей).Эта функция растет медленнее, чем 2cn при любой константе c > 0, поскольку cn вконце концов превышает (log2 n)2, какой бы малой ни была c.Неформально графы представляются как диаграммы, наподобие изображенной нарис. 10.1. У них есть узлы, которые в данном примере графа пронумерованы 1–4, и ребра, соединяющие некоторые пары узлов. Каждое ребро имеет целочисленный вес. Остовное дерево — это подмножество ребер, с помощью которых соединены все узлы, ноциклы отсутствуют. Пример остовного дерева показан на рис. 10.1 — это три ребра, выделенные жирными линиями.
Остовное дерево минимального веса — это дерево наименьшего общего веса среди всех остовных деревьев.12115210320184Рис. 10.1. Граф, в котором остовное дерево минимальноговеса выделено жирными линиями10.1. ÊËÀÑÑÛ P È NPСтр. 425425Для нахождения ОДМВ существует хорошо известный “жадный” алгоритм, которыйназывается алгоритмом Крускала1. Опишем вкратце его основные идеи.1.Для каждого узла определяется компонент связности, который содержит этот узел иобразован с использованием ребер, выбранных до сих пор. Вначале не выбрано ниодно ребро, так что каждый узел образует отдельный компонент связности.2.Среди еще не выбранных ребер рассмотрим ребро минимального веса.
Если оно соединяет два узла, которые в данный момент принадлежат различным компонентамсвязности, то выполняется следующее:а) ребро добавляется в остовное дерево;б) связные компоненты сливаются (объединяются) путем замены номера компонента у всех узлов одного из них номером другого.Если же выбранное ребро соединяет узлы из одного и того же компонента, то это реброне принадлежит остовному дереву; его добавление привело бы к образованию цикла.Выбор ребер продолжается до тех пор, пока мы не выберем все ребра, или число ребер, выбранных в остовное дерево, не станет на единицу меньше общего числа узлов. Заметим, что в последнем случае все узлы должны принадлежать одному компоненту связности, и процесс выбора ребер можно прекратить.3.Пример 10.1.
В графе на рис. 10.1 сначала рассматривается ребро (1, 3), посколькуоно имеет минимальный вес — 10. Так как вначале 1 и 3 принадлежат разным компонентам, это ребро принимается, а узлам 1 и 3 приписывается один и тот же номер компонента, скажем, “компонент 1”. Следующее по порядку возрастания веса ребро — (2, 3) с весом 12. Поскольку 2 и 3 принадлежат разным компонентам, то это ребро принимается, и2 добавляется в “компонент 1”.
Третье ребро — (1, 2) с весом 15. Но узлы 1 и 2 уже находятся в одном компоненте, поэтому данное ребро отбрасывается, и мы переходим кчетвертому ребру — (3, 4). Поскольку 4 не содержится в “компоненте 1”, данное ребропринимается. Теперь у нас есть остовное дерево из трех ребер, и можно остановиться. Этот алгоритм обработки графа с m узлами и e ребрами можно реализовать (с помощью компьютера, а не машины Тьюринга) за время O(m + e log e). Более простая реализация имеет e этапов. Номер компонента каждого узла хранится в некоторой таблице.Выбор ребра наименьшего веса среди оставшихся занимает время O(e), а поиск компонентов, в которых находятся узлы, связанные этим ребром, — O(m). Если эти узлы принадлежат различным компонентам, то на просмотр таблицы для объединения всех узловс соответствующими номерами нужно время O(m).
Таким образом, общее время работыэтого алгоритма — O(e(e + m)). Это время полиномиально зависит от “размера” входныхданных, в качестве которого можно неформально выбрать сумму e и m.1J. B. Kruskal Jr., “On the shortest spanning subtree of a graph and the traveling salesman problem”,Proc. AMS 7:1 (1956), pp.48–50.426Стр.
426ÃËÀÂÀ 10. ÒÐÓÄÍÎÐÅØÀÅÌÛÅ ÏÐÎÁËÅÌÛПри перенесении изложенных идей на машины Тьюринга возникают следующие вопросы.• Выход алгоритмов разрешения различных проблем может иметь много разныхформ, например, список ребер ОДМВ. Проблемы же, решаемые машинами Тьюринга, можно интерпретировать только как языки, а их выходом может бытьтолько ДА или НЕТ (допустить или отвергнуть). Например, проблему поискаОДМВ можно перефразировать так: “Для данного графа G и предельного числаW выяснить, имеет ли G остовное дерево с весом не более W?”. Может показаться, что эту проблему решить легче, чем проблему ОДМВ в знакомой нам формулировке, поскольку не нужно даже искать остовное дерево.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
