dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 96
Текст из файла (страница 96)
Однако в рамках теории труднорешаемости нам, как правило, нужно доказать, что проблема трудна(не легка). А из того, что “да/нет”-версия проблемы трудна, следует, что трудна иее версия, предполагающая полный ответ.• Хотя “размер” графа можно неформально представить себе как число его узловили ребер, входом МТ является цепочка в некотором конечном алфавите. Поэтому такие элементы, фигурирующие в проблеме, как узлы и ребра, должныбыть подходящим образом закодированы.
Выполняя это требование, получаемв результате цепочки, длина которых несколько превышает предполагаемый“размер” входа. Однако есть две причины проигнорировать эту разницу.1.Размеры входной цепочки МТ и входа неформальной проблемы всегда отличаютсяне более, чем малым сомножителем, обычно — логарифмом размера входных данных.
Таким образом, все, что делается за полиномиальное время с использованиемодной меры, можно сделать за полиномиальное время, используя другую меру.2.Длина цепочки, представляющей вход, — в действительности более точная мерачисла байтов, которые должен прочитать реальный компьютер, обрабатывая свойвход. Например, если узел задается целым числом, то количество байтов, необходимых для представления этого числа, пропорционально его логарифму, а это не “1байт на каждый узел”, как можно было бы предположить при неформальном подсчете размера входа.Пример 10.2. Рассмотрим код для графов и предельных весов, который может бытьвходом для проблемы ОДМВ. В коде используются пять символов: 0, 1, левая и праваяскобки, а также запятая.1.Припишем всем узлам целые числа от 1 до m.2.В начало кода поместим значения m и предельного веса W в двоичной системе счисления, разделенные запятой.3.Если существует ребро, соединяющее узлы i и j и имеющее вес w, то в код записывается тройка (i, j, w), где целые числа i, j и w кодируются в двоичном виде.
Порядокзаписи узлов ребра и порядок ребер в графе не играют роли.10.1. ÊËÀÑÑÛ P È NPСтр. 427427Таким образом, один из возможных кодов графа на рис. 10.1 с предельным весом W = 40имеет вид100, 101000(1, 10, 1111)(1, 11, 1010)(10, 11, 1100)(10, 100, 10100)(11, 100, 10010).Если кодировать входы проблемы ОДМВ так, как в примере 10.2, то вход длины nможет представлять максимум O(n/log n) ребер.
Если число ребер очень мало, то числоузлов m может быть экспоненциальным относительно n. Однако если число ребер eменьше m – 1, то граф не может быть связным, и независимо от того, каковы эти ребра,не имеет ОДМВ. Следовательно, если количество узлов превосходит число n/log n, то нетникакой необходимости запускать алгоритм Крускала — мы просто говорим: “нет, остовного дерева с таким весом не существует”.Итак, пусть у нас есть верхняя граница времени работы алгоритма Крускала, выражаемая в виде функции от m и e, например, как найденная выше верхняя границаO(e(e + m)). Можно изменить m и e на n и сказать, что время работы выражаетсяфункцией от длины входа n, имеющей вид O(n(n + n)) или O(n 2). В действительности, более удачная реализация алгоритма Крускала требует времени O(n log n), носейчас это не важно.Представленный алгоритм Крускала предназначен для реализации на языке программирования с такими удобными структурами данных, как массивы и указатели, но в качестве модели вычислений мы используем машины Тьюринга.
Тем не менее, описаннуювыше версию алгоритма можно реализовать за O(n2) шагов на многоленточной машинеТьюринга. Дополнительные ленты используются для выполнения нескольких вспомогательных задач.1.На одной из лент можно хранить информацию об узлах и их текущих номерах компонентов. Длина такой таблицы составит O(n).2.Еще одна лента может применяться в процессе просмотра входной ленты для хранения информации о ребре, имеющем на данный момент наименьший вес среди ребер,не помеченных как “использованные” (выбранные). С помощью второй дорожкивходной ленты можно отмечать те ребра, которые были выбраны в качестве ребернаименьшего веса на одном из предыдущих этапов работы алгоритма. Поиск непомеченного ребра наименьшего веса занимает время O(n), поскольку каждое реброрассматривается лишь один раз, и сравнить вес можно, просматривая двоичные числа линейно, справа налево.3.Если ребро на некотором этапе выбрано, то соответствующие два узла помещаютсяна ленту.
Чтобы установить компоненты этих двух узлов, нужно просмотреть таблицу узлов и компонентов. Это займет O(n) времени.4.Еще одна лента может хранить информацию об объединяемых компонентах i и j, когданайденное ребро соединяет различающиеся на данный момент компоненты. В этом428Стр. 428ÃËÀÂÀ 10.
ÒÐÓÄÍÎÐÅØÀÅÌÛÅ ÏÐÎÁËÅÌÛслучае просматривается таблица узлов и компонентов, и для каждого узла из компонента i номер компонента меняется на j. Эта процедура также занимает O(n) времени.Теперь нетрудно самостоятельно завершить доказательство, что на многоленточнойМТ каждый этап работы алгоритма может быть выполнен за время O(n).
Поскольку число этапов e не превышает n, делаем вывод, что времени O(n2) достаточно для многоленточной МТ. Теперь вспомним теорему 8.10, утверждавшую, что работу, которую многоленточная МТ выполняет за s шагов, можно выполнить на одноленточной МТ за O(s2)шагов.
Таким образом, если многоленточной МТ требуется сделать O(n2) шагов, то можно построить одноленточную МТ, которая делает то же самое за O((n2)2) = O(n4) шагов.Следовательно, “да/нет”-версия проблемы ОДМВ (“имеет ли граф G ОДМВ с общим весом не более W?”) принадлежит P.10.1.3. Íåäåòåðìèíèðîâàííîå ïîëèíîìèàëüíîå âðåìÿФундаментальный класс проблем в изучении труднорешаемости образован проблемами, разрешимыми с помощью недетерминированной МТ за полиномиальное время.Формально, мы говорим, что язык L принадлежит классу NP (недетерминированный полиномиальный), если существуют недетерминированная МТ M и полиномиальная временная сложность T(n), для которых L = L(M), и у M нет последовательностей переходовдлиной более T(n) при обработке входа длины n.Поскольку всякая детерминированная МТ представляет собой недетерминированнуюМТ, у которой нет возможности выбора переходов, то P ⊆ NP. Однако оказывается, чтов NP содержится множество проблем, не принадлежащих P.
Интуиция подсказывает:причина в том, что НМТ с полиномиальным временем работы имеет возможность угадывать экспоненциальное число решений проблемы и проверять “параллельно” каждоеиз них за полиномиальное время. И все-таки,• одним из самых серьезных нерешенных вопросов математики является вопрос отом, верно ли, что P = NP, т.е. все, что с помощью НМТ делается за полиномиальное время, ДМТ в действительности также может выполнить за полиномиальное время (которое, возможно, выражается полиномом более высокой степени).10.1.4.
Ïðèìåð èç NP: ïðîáëåìà êîììèâîÿæåðàДля того чтобы осознать, насколько обширен класс NP, рассмотрим пример проблемы,которая принадлежит классу NP, но, предположительно, не принадлежит P, — проблемукоммивояжера (ПКОМ). Вход ПКОМ (как и у ОДМВ) — это граф, каждое ребро которогоимеет целочисленный вес (рис. 10.1), а также предельный вес W. Вопрос состоит в том,есть ли в данном графе “гамильтонов цикл” с общим весом, не превышающим W. Гамиль10.1.
ÊËÀÑÑÛ P È NPСтр. 429429тонов цикл — это множество ребер, соединяющих узлы в один цикл, причем каждыйузел встречается в нем только один раз. Заметим, что число ребер в гамильтоновом цикле должно равняться числу узлов графа.Îäíà èç âåðñèé íåäåòåðìèíèðîâàííîé äîïóñòèìîñòèЗаметим, что мы требовали останова нашей НМТ за полиномиальное время на любойиз ветвей (ее работы), независимо от того, допускает она или нет. Можно было бытакже установить полиномиальное ограничение во времени T(n) лишь для тех ветвей,которые ведут к допусканию, т.е. определить NP как класс языков, допускаемыхНМТ, которые допускают с помощью хотя бы одной последовательности переходовдлиной не более T(n), где T(n) — некоторый полином.Однако в результате мы получили бы тот же самый класс языков, и вот почему.
Еслинам известно, что M, если вообще допускает, делает это в результате T(n) переходов,то ее можно модифицировать так, чтобы на отдельной дорожке ленты она вела счетдо T(n) и останавливалась, не допуская, если счет превысит T(n). Число шагов модифицированной M могло бы достигать O(T2(n)). Но если T(n) — полином, то и T2(n) —полином.В действительности, класс P можно было бы также определить с помощью машинТьюринга, допускающих за время T(n), где T(n) есть некоторый полином.
Эти МТмогли бы не останавливаться, не допуская. Но с помощью такой же конструкции, каки для НМТ, мы могли бы модифицировать ДМТ так, чтобы она считала до T(n) и останавливалась, перейдя эту границу. Время работы такой ДМТ было бы O(T2(n)).Пример 10.3. Граф, изображенный на рис. 10.1, имеет в действительности лишь одингамильтонов цикл — (1, 2, 4, 3, 1). Его общий вес составляет 15 + 20 + 18 + 10 = 63. Таким образом, если W имеет значение 63 или больше, то ответ — “да”, а если W < 63, тоответ — “нет”.Однако простота ПКОМ для графа с четырьмя узлами обманчива.
В данном графепопросту не может быть более двух различных гамильтоновых циклов, учитывая, чтоодин и тот же цикл может иметь начало в разных узлах и два направления обхода. Но вграфе с m узлами число различных циклов достигает O(m!), факториала числа m, чтопревышает 2cm для любой константы c. Оказывается, что любой способ решения ПКОМ включает перебор, по сути, всехциклов и подсчет общего веса каждого из них. Можно поступить умнее, отбросив некоторые, очевидно неподходящие, варианты. Однако, по всей видимости, при любых наших усилиях все равно придется рассматривать экспоненциальное число циклов передтем, как убедиться в том, что ни один из них не имеет вес меньше предельного W, илиотыскать такой цикл.430Стр. 430ÃËÀÂÀ 10.
ÒÐÓÄÍÎÐÅØÀÅÌÛÅ ÏÐÎÁËÅÌÛС другой стороны, если бы у нас был недетерминированный компьютер, то можнобыло бы “угадать” перестановку узлов и вычислить общий вес цикла, образованного узлами в этом порядке. Если бы существовал реальный недетерминированный компьютер,то при обработке входа длины n ни на одной из ветвей ему не пришлось бы сделать более O(n) шагов. На многоленточной НМТ перестановку можно угадать за O(n2) шагов, истолько же времени понадобится для проверки ее общего веса. Таким образом, одноленточная НМТ может решить ПКОМ за время, не превышающее O(n4). Делаем вывод, чтоПКОМ принадлежит классу NP.10.1.5.
Ïîëèíîìèàëüíûå ñâåäåíèÿОсновной метод доказательства того, что проблему P2 нельзя решить за полиномиальное время (т.е. P2 не принадлежит P), состоит в сведении к ней проблемы P1, относительно которой известно, что она не принадлежит P.2 Данный подход был представленна рис. 8.7, который воспроизводится здесь в виде рис. 10.2.ЭкземплярПостроениеЭкземплярРазрешениеРис. 10.2. Повторение картины сведенияДопустим, что мы хотим доказать утверждение: “если P2 принадлежит P, то и P1 принадлежит P”. Поскольку мы утверждаем, что P1 не принадлежит P, можно будет утверждать, что и P2 не принадлежит P.
Однако одного лишь существования алгоритма, обозначенного на рис. 10.2 как “Построение”, не достаточно для доказательства нужногонам утверждения.В самом деле, пусть по входному экземпляру проблемы P1 длиной m алгоритм вырабатывает выходную цепочку длины 2m, которая подается на вход гипотетическому алгоритму, решающему P2 за полиномиальное время. Если решающий P2 алгоритм делаетэто, скажем, за время O(nk), то вход длиной 2m он обработает за время O(2km), экспонен-2Это утверждение не совсем верно. В действительности мы лишь предполагаем, что P1 не при-надлежит P, на том весьма веском основании, что P1 является “NP-полной” (понятие “NPполноты” обсуждается в разделе 10.1.6).
Затем мы доказываем, что P2 также является “NP-полной”и, таким образом, не принадлежит P на том же основании, что и P1.10.1. ÊËÀÑÑÛ P È NPСтр. 431431циальное по m. Таким образом, алгоритм, решающий P1, обрабатывает вход длиной m завремя, экспоненциальное по m. Эти факты целиком согласуются с ситуацией, когда P2принадлежит P, а P1 — нет.Даже если алгоритм, переводящий экземпляр P1 в экземпляр P2, всегда вырабатываетэкземпляр, длина которого полиномиальна относительно длины входа, то мы все равноможем не добиться желаемого результата. Предположим, что построенный экземпляр P2имеет ту же длину m, что и P1, но сам алгоритм преобразования занимает время, экспоненциальное по m, скажем, O(2m). Тогда из того, что алгоритм решения P2 тратит на обработку входа длиной n время O(nk), следует лишь то, что существует алгоритм решенияP1, которому для обработки входа длиной m нужно время O(2m + mk).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
