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

NP-ПОЛНЫЕ ЗАДАЧИ

Сколько вычислений должна требовать задача, чтобы мы сочли ее действительно трудной? Общепринято, что если задачу нельзя решить быстрее, чем за экспоненциальное время, то ее следует рассматривать как безусловно трудно разрешимую. В этой "схеме классификации" задачи, решаемые алгоритмами полиномиальной сложности, будут легко разрешимыми. Но нужно иметь в виду, что, хотя экспоненциальная функция (такая, как 2") растет быстрее любой полиномиальной функции от п, для небольших значений п алгоритм, требующий 0(2") времени, может оказаться эффективнее многих алгоритмов с полиномиально ограниченным временем работы. Например, сама функция 2" не превосходит п" до значения п, равного 59. Тем не менее скорость роста экспоненциальной функции столь стремительна, что мы будем называть задачу трудно разрешимой, если у всех алгоритмов, решающих ее, сложность по меньшей мере экспоненциальна.

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

Мы исследуем также еще один класс задач, называемых "полными для полиномиальной емкости", которые по меньшей мере столь же сложны, как NP-полные задачи, но и про них еще не доказано, что



) Читателю, недостаточно хорошо знакомому с машинами Тьюринга, предлагаем освежить в памяти разд. 1.6.

ОНИ трудно разрешимы. В гл. 11 будут изложены некоторые задачи, относительно которых действительно можно доказать, что они трудно разрешимы.

10.1. НЕДЕТЕРМИНИРОВАННЫЕ МАШИНЫ ТЬЮРИНГА

По причинам, которые скоро станут ясными, ключевое понятие в теории NP-полных задач - недетерминированная машина Тьюринга ). Мы уже обсуждали недетерминированные конечные автоматы, у которых каждый шаг может перевести автомат в несколько различных состояний. По аналогии недетерминированная машина Тьюринга имеет конечное число возможных шагов, из которых в очередной момент выбирается какой-то один. Входная цепочка X допускается, если по крайней мере одна последовательность шагов для входа X приводит к допускающему мгновенному описанию (МО).

При данной входной цепочке х можно считать, что недетерминированная машина Тьюринга М параллельно выполняет все возможные последовательности шагов, пока не достигнет допускающего МО или пока не окажется, что дальнейшие шаги невозможны. Иначе говоря, после i шагов можно считать, что существуют много экземпляров М. Каждый экземпляр представляет МО, в котором М может оказаться после i шагов. На (i+l)-M шаге экземпляр С порождает / своих экземпляров, если машина Тьюринга, находясь в МО С, может выбрать следующий шаг / способами.

Таким образом, возможные последовательности шагов машины М на входе х можно организовать в виде дерева мгновенных описаний. Каждый путь из корня в лист этого дерева представляет некоторую последовательность возможных шагов. Если о - кратчайшая последовательность шагов, которая оканчивается допускающим МО, то, как только машина М сделает а шагов, она остановится и допустит вход X. Время, затрачиваемое на обработку входа X, равно длине последовательности а. Если на входе х никакая последовательность шагов не приводит к допускающему МО, то М отвергает х, а время, затрачиваемое на обработку х, не определено.

Часто удобно представлять себе, что М "угадывает" только шаги из последовательности а и проверяет, что а на самом деле оканчивается допускающим МО. Но поскольку детерминированная машина обычно не может заранее угадать допускающую последовательность шагов, то детерминированное моделирование машины М потребовало бы просмотра в некотором порядке дерева всех возможных последовательностей шагов на входе х и этот просмотр продолжался бы до обнаружения кратчайшей последовательности, окан-



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

Определение, k-ленточной недетерминированной машиной Тьюринга (для краткости НМТ) М называют семерку (Q, Т, I, б, Ь, 0, (}f), где значения всех компонент те же, что и для обычной детерминированной машины Тьюринга, за исключением того, что здесь функция переходов б представляет собой отображение множества QxT* в множество подмножеств в Qx{Tx{L, R, S})*. (L означает сдвиг головки влево, R - вправо, S - головка остается на месте.) Иными словами, поданному состоянию и списку из k ленточных символов функция б выдает конечное множество вариантов следующего шага; каждый вариант состоит из нового состояния, k новых ленточных символов и k сдвигов головок. Заметим, что НМТ М может выбрать любой из этих вариантов шага, но не может выбрать следующее состояние из одного шага, а новые ленточные символы - из другого или устроить какую-нибудь еще комбинацию вариантов шага.

Мгновенные описания для НМТ определяются точно так же, как и для детерминированной машины Тьюринга (ДМТ). Данная НМТ M=(Q, Т, I, б, Ь, 0, ?f) делает шаг, исходя из своего текущего состояния, скажем д, и символов, обозреваемых каждой из k головок, скажем Хи Х,. . ., Х. Из множества b{q, Хи X....., Х)

она выбирает некоторый элемент (г, (Yu Di),. . ., [Y, D)). Этот элемент указывает, что новым состоянием должно стать г, на г-й ленте следует напечатать вместо Xj и головку сдвинуть в направлении, обозначенном знаком Di, 1<1</г. Если при некотором выборе следующего шага МО С переходит в МО D, то пишут С1- (или C\-D, если ясно, о какой машине М идет речь). Заметим, что для данной НМТ М может быть несколько таких D, что С \- D, но если машина М детерминированна, то для каждого С существует не более одного такого D.

Запись Ci\-* С означает, что для некоторого k выполняется Ci I- Сг I- . . . 1- Cft=C или Ci=C. НМТ М допускает цепочку w, если (даШ, до, q,. .., qo) Н* («ь «г,- • «*), где (и, значит, а„ ...





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.0039