1610906280-c80d8404f2eaa01776b47d41b0f18e85 (824375), страница 23
Текст из файла (страница 23)
Недетерминированная машина Тьюринга T = hA, Q, P, q1 , q0 i называется полиномиально ограниченной над алфавитом A0 ⊆ A \ {0}, если существуетполином p(n) с натуральными коэффициентами, такой, что для любого слова w ∈ A∗0p(|w|)+1не существует конфигурации M с условием q1 0w0 `TM.Другими словами, любое вычисление машины заканчивается не более чем заp(|w|) шагов, где |w| — длина входного слова.Определение. Язык L ⊆ A∗0 называется полиномиально распознаваемым на детерминированной машине Тьюринга, если существует детерминированная полиномиально ограниченная над алфавитом A0 машина Тьюринга T , которая распознаетязык L.Через P обозначим класс всех языков, полиномиально распознаваемых на детерминированных машинах Тьюринга.Определение. Язык L ⊆ A∗0 называется полиномиально распознаваемым на недетерминированной машине Тьюринга, если существует недетерминированная полиномиально ограниченная над алфавитом A0 машина Тьюринга T , которая распознаетязык L.Через NP обозначим класс всех языков, полиномиально распознаваемых на недетерминированных машинах Тьюринга.Пример.
Вернемся к примеру из предыдущего параграфа. Мы построили недетерминированную машину Тьюринга T , которая распознает язык L = {an | n — составное число } над алфавитом A0 = {a}.Допустим, на вход машины T подана начальная конфигурация q1 0an 0, т. е. длинавходного слова равна n.
Оценим сверху максимально возможную длину вычисленияна построенной машине с данной начальной конфигурацией.Недетерминированная часть вычисления, т. е. цепочка преобразований:q1 0an 0 `∗ 0bk−2 q4 b0an−k 0 = 00sk+t bk−2−t q4 b0bt an−(s+1)k−t 0,94Глава V. Теория сложности алгоритмовгде s = t = 0, очевидно осуществляется за k + 1 шагов.Далее, как мы уже говорили, запускается двойная циклическая структура.
В цепочке преобразований00sk+t bk−2−t q4 b0bt an−(s+1)k−t 0 `∗ 00sk+t q5 bk−1−t 0bt an−(s+1)k−t 0 `` 00sk+t 0q6 bk−2−t 0bt an−(s+1)k−t 0 `∗ 00sk+t 0bk−2−t 0q7 bt an−(s+1)k−t 0использовано ровно 2(k −t) шагов. Если в состоянии q7 обозревается 0, то происходитнеправильная остановка, но длина такого вычисления не является максимальной.Иначе у нашей цепочки будет продолжение00sk+t+1 bk−2−t 0q7 bt an−(s+1)k−t 0 `∗ 00sk+t+1 bk−2−t q8 0bt+1 an−(s+1)k−(t+1) 0,в которой использовано 2t + 1 шагов. Далее из состояния q8 машина переходит за 1шаг в состояние q9 и смещается на ячейку влево.
Если в состоянии q9 обозревается b,то машина переходит за 1 шаг на следующую итерацию во внутреннем цикле. Такимобразом, одна итерация внутреннего цикла осуществляется за 2(k − t) + (2t + 1) + 2 =2k + 3 шага. Внутренний счетчик принимает значения t = 0, . . . , k − 2.Если же в состоянии q9 обозревается 0, то, значит, t = k − 2 и цепочка имеетпродолжение00(s+1)k−2 q9 00bk−1 an−(s+2)k+1 0 `∗ 00(s+1)k bk−1 q11 an−(s+2)k+1 0,в котором насчитывается k+1 шагов. Если в состоянии q11 обозревается 0, то происходит неправильная остановка, но длина такого вычисления не является максимальной.Иначе цепочка продолжается так (здесь использован 1 шаг):00(s+1)k bk−1 q11 an−(s+2)k+1 0 ` 00(s+1)k bk−1 0q12 an−(s+2)k 0.Если в состоянии q12 обозревается 0, то, значит, k делит n, машина производит правильную остановку и выдает 1.
Иначе машина после исполнения последних двухкоманд, т. е. за 2 шага, переходит на следующую итерацию во внешнем цикле.Таким образом, внешний цикл состоит из k − 1 повторений внутреннего цикла ииз дополнительных k + 5 шагов. Всего в одной итерации внешнего цикла получается(k − 1)(2k + 3) + k + 5 = 2k 2 + 2k + 2 шагов.Внешний счетчик в самом худшем случае принимает значения s = 0, .
. . , [ nk ]. Следовательно, учитывая шаги из стартовой части вычислений, получаем, что общеечисло шагов в вычислении не превосходитhni2k + 1 + (2k + 2k + 2)(+ 1) 6 n + 1 + (2n2 + 2n + 2)(n + 1) = 2n3 + 4n2 + 5n + 3.kСледовательно, длина вычислений ограничена сверху полиномом p(n) = 2n3 + 4n2 +5n + 3 и, значит, язык L полиномиально распознаваем на недетерминированной машине Тьюринга, т. е.
L ∈ NP.Теперь мы сформулируем некоторые важные свойства классов P и NP.Предложение 74. Имеет место включение P ⊆ NP.Доказательство. Очевидно, поскольку детерминированные машины Тьюринга являются частным случаем недетерминированных.§ 25. Классы P и NP95Замечание. Вопрос о справедливости обратного включения NP ⊆ P является однойиз важнейших нерешенных проблем современной математики, которую очень частообозначают как ПРОБЛЕМА «P = NP?».Для машин Тьюринга справедлива теорема о детерминизации, т. е.
для любойнедетерминированной машины Тьюринга, распознающей некоторый язык L, существует детерминированная машина Тьюринга, которая распознает тот же самый язык L. Доказательство данной теоремы можно найти в [12]. Таким образом,класс всех языков, распознаваемых недетерминированными машинами Тьюринга,совпадает с классом всех языков, распознаваемых детерминированными машинамиТьюринга, но данный факт никак не решает проблему «P = NP?».
Причина этогозаключается в том, что процедура детерминизации недетерминированной машиныТьюринга очень сильно увеличивает временную сложность машины. Наименьшаяверхняя граница сложности, которая возникает после применения процедуры детерминизации, экспоненциальная.Предложение 75. Класс P замкнут относительно дополнения.Доказательство.
Пусть язык L ⊆ A∗0 принадлежит классу P. Следовательно, найдется детерминированная полиномиально ограниченная над алфавитом A0 ⊆ A\ {0}машина Тьюринга T = hA, Q, P, q1 , q0 i, которая распознает язык L.Определим машину Тьюринга T 0 = hA, Q0 , P 0 , q1 , q00 i, где Q0 = Q ∪ {q00 }, P 0 =P ∪ {q0 0 → q00 1, q0 1 → q00 0, . . . }. Другими словами, мы добавили в машину T новоезаключительное состояние q00 и две команды q0 0 → q00 1 и q0 1 → q00 0 (конкретный видкоманд q0 ai → .
. ., где ai ∈/ {0, 1}, не имеет значения).Ясно, что определенная таким образом машина T 0 полиномиально ограниченанад алфавитом A0 и распознает дополнение A∗0 \ L.Замечание. Отметим без доказательства, что класс P замкнут также относительнообъединения, пересечения, конкатенации и звездочки Клини.Класс NP также замкнут относительно объединения, пересечения, конкатенации извездочки Клини. Однако вопрос о замкнутости класса NP относительно дополнениядо сих пор является открытым и тесно связан с проблемой «P = NP?».Предложение 76. Если класс NP не замкнут относительно операции дополнения,то P 6= NP.Доказательство. Допустим, существует язык L такой, что L ∈ NP, но его допол/ NP. Докажем, что в этом случае L ∈/ P. Если, напротив, L ∈ P, то внение L ∈силу предложения 75 L ∈ P.
Следовательно, в силу предложения 74 заключаем, чтоL ∈ NP, что противоречит нашему первоначальному предположению.В заключение параграфа докажем, что класс P нетривиален, т. е. является собственным подклассом в классе всех языков, распознаваемых (детерминированнымиили недетерминированными) машинами Тьюринга.Теорема 77. Существует распознаваемый машиной Тьюринга язык L, не принадлежащий классу P.Доказательство. Для определения требуемого языка L нам необходимо закодировать каждую машину Тьюринга в виде слова над некоторым алфавитом.
Пусть96Глава V. Теория сложности алгоритмовc = qi aj → qk al S, где S ∈ {Λ, R, L}, — произвольная команда машины Тьюринга.Сопоставим ей словоbc = 1i | 1j | 1k | 1l | 1s ,где s = 0, если S = Λ; s = 1, если S = R; и s = 2, если S = L. Если теперь T —произвольная детерминированная машина Тьюринга с программой {c1 , . .
. , cm }, тосопоставим ей словоTb = cb1 k cb2 k . . . k ccm.Зафиксируем алфавит A0 = {1, |, k} и рассмотрим над этим алфавитом следующий язык:L = {Tb | машина Тьюринга T перерабатывает конфигурациюq1 0Tb0 в конфигурацию uq0 1v для некоторых u и v,bне более, чем за 2|T | шагов}.Язык L распознаваем машиной Тьюринга. Действительно, существует интуитивно вычислимая процедура (машина Тьюринга), которая по произвольному слову wнад алфавитом A0 сначала проверяет, является ли оно словом вида Tb для какойлибо детерминированной машины T . Затем, если w имеет вид Tb, данная процедуравосстанавливает программу T и проверяет, действительно ли она перерабатываетbконфигурацию q1 0Tb0 в конфигурацию вида uq0 1v не более, чем за 2|T | шагов.
Описанную процедуру можно смоделировать на машине Тьюринга.Допустим теперь, что L ∈ P. Следовательно, по предложению 75 язык L полиномиально распознается на некоторой детерминированной машине Тьюринга M . Пустьp(x) — соответствующий полином из определения полиномиальной ограниченностиM . Без ограничения общности можно считать, чтоcc|) < 2|M | .p(|MДействительно, поскольку p(n)→ 0 при n → ∞, найдется n0 ∈ ω такое, что для2nвсех n > n0 выполняется p(n) < 2n .
Отсюда следует, что, добавив в машину Mнеобходимое число фиктивных состояний и команд (т. е. команд, не влияющих наc| так, чтобы имело место неравенствоработу машины), мы можем увеличить число |Mc|c| > n0 , из которого вытекает справедливость условия p(|Mc|) < 2|M|M.cc ∈ LИсследуем теперь вопрос принадлежности слова M языку L. Условие Mэквивалентно следующему условию:c0 в конфигурацию uq0 1v для1) Машина M перерабатывает конфигурацию q1 0Mcнекоторых u и v не более, чем за 2|M | шагов.c0, всегда останавПоскольку машина M , будучи запущенная из конфигурации q1 0Mc|c|) < 2|Mливается не более, чем за p(|Mшагов, то условие (1) равносильно следующему условию:c0 в конфигурацию вида uq0 1v.2) Машина M перерабатывает конфигурацию q1 0MНаконец, вспомним, что машина M распознает язык L.
Отсюда вытекает, что условиеc∈(2) эквивалентно условию M/ L.c ∈ L ⇐⇒ Mc∈Таким образом, имеет место эквивалентность M/ L. Противоречие.Следовательно, L ∈/ P.§ 26. NP-полные проблемы§ 26.97NP-полные проблемыЕще никому не удалось доказать, что существует язык из класса NP, не принадлежащий классу P. Проблема «P = NP?» по-прежнему остается открытой. Однако можнодоказать, что некоторые языки не менее «трудны», чем любой язык из NP, в томсмысле, что если бы у нас был детерминированный алгоритм, распознающий одиниз этих «не менее трудных» языков за полиномиальное время, то можно было бы длякаждого языка из класса NP найти детерминированный алгоритм, распознающий егоза полиномиальное время. Такие языки называются NP-полными.Для определения NP-полноты необходимо сначала ввести понятие полиномиальной сводимости, которое в свою очередь использует понятие полиномиально вычислимой функции.Определение.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
