А.А. Сапоженко - Некоторые вопросы сложности алгоритмов (PDF) (1132758), страница 4
Текст из файла (страница 4)
При изложении использовались источники [1],[2] и [3].Существует большой класс вычислительных задач, заключающийся враспознавании тех или иных свойств графов, целых чисел, массивов целыхчисел (векторов, матриц и т.п.), конечных множеств, булевых формул и др.Посредством кодирования таких объектов множествами слов эти задачи могут быть превращены в задачи распознавания языков.
Тем самым вопрос осложности самых разнообразных вычислительных задач сводится к вопросуо сложности распознавания языков.Принято считать, что задача решается эффективно, если существует алгоритм ее решения со временем работы, которое ограничено полиномом отразмера входных данных. Впервые эту рабочую гипотезу выдвинул и сталзащищиать Джек Эдмондс [4]. Теорема Ст. Кука и понятие полиномиальнойсводимости позволяют доказать, что большой класс (т.н.
N P -полных) задач,ни для одной из которых пока (к 2001г.) не удалось найти полиномиальногоалгоритма, эквивалентны между собой в том смысле, что либо каждая из нихрешается эффективно, либо ни одна из них такого решения не имеет.Определения. Термин “машина Тьюринга” (сокращенно МТ) употребляется здесь для одноленточных детерминированных машин, (см., например,[5]). Некоторое (непринципиальное) отличие состоит в том, что мы рассматриваем МТ с односторонней лентой, бесконечной вправо. Алфавит ленты МТобозначим через A, а множество состояний — через Q. Символом q1 обозначается начальное состояние, символом a1 — пустой символ, присутствующийпо определению в алфавите A.
Считается, что в начальный момент слово,w = b1 , b2 , ..., bn , обрабатываемое МТ, записано в первых n ячейках ленты,а все остальные ячейки ленты содержат символ a1 . ДетерминированностьМТ означает, что для каждой пары вида (a, q), где a — символ входногоалфавита, а q — символ состояния, в программе МТ присутствует не болееодной команды вида: aq → a0 q 0 d, начинающейся с aq.Пусть в процессе работы МТ на некотором такте t оказалось, что на лентезаписано слово w = b1 , b2 , ..., bm , МТ находится в состоянии qj , головка МТобозревает ячейку с номером k. Конфигурацией (мгновенным описанием),соответствующей этому такту t, называется слово вида Ct = b1 , b2 , ..., bk−1 ,qj , bk , ..., bm . Конфигурация, соответствующая первому такту, называется начальной, а последнему (если МТ останавливается), — заключительной.
Вы19числением МТ M на входе w называется последовательность конфигурацийC1 , C2 , ..., Ct , ..., возникающая при работе над словом w. Подразумевается,что конфигурация Ct+1 однозначно определяется конфигурацией Ct и командой МТ M , начинающейся с пары (bk , qj ), где bk — символ, обозреваемый МТв момент t, а qj — состояние МТ в момент t. Время работы или число шаговtM (w) МТ M на входе w определяется как число конфигураций в вычислении МТ M на входе w. Если вычисление бесконечно, полагаем tM (w) = ∞.Пусть среди состояний МТ имеются выделенные заключительные состояния— принимающее и отвергающее.
Тогда вычисление называется принимающим (отвергающим), если оно заканчивается в принимающем (отвергающем) состоянии.Недетерминированные Машины Тьюринга. Отличие недетерминированной МТ (сокращенно, НМТ) от детерминированной состоит в том, чтов программе НМТ для пары (a, q), где a — символ из алфавита МТ, а q —символ состояния, в ее программе может присутствовать несколько (но неболее некоторого фиксированнного для заданной МТ числа) команд, начинающихся с aq. Без потери общности можно ограничиться случаем, когда пареaq может соответствовать не более двух команд c началом aq.
Пусть в программе НМТ имеется пара команд aq → a0 q 0 L и aq → a00 q 00 R. Тогда, находясьв состоянии q и обозревая символ a на ленте, НМТ может выбрать любуюиз двух возможностей: записать в обозреваемую ячейку символ a0 , перейти всостояние q 0 и сдвинуть головку влево, либо записать в обозреваемую ячейкусимвол a00 , перейти в состояние q 00 и сдвинуть головку вправо.
При этом считается что НМТ как бы создает две копии самой себя и прослеживает последовательность вычислений обоих способов действия. Понятие конфигурациидля НМТ не отличается от того, что определено выше. Вычислением НМТна входе w называется последовательность конфигураций C1 , C2 , ..., Ct , ..., cC1 = q1 w и такая, что Ct+1 получается из Ci с помощью одной из команд, соответствующих паре a(i)q(i), где q(i) — символ состояния, входящий в Ci , аa(i) — буква из Ci , стоящая справа от q(i). Всякое вычисление можно изобразить ориентированной цепью, вершинами которой являются конфигурации,а каждая дуга соединяют две последовательные вершины.
В случае детерминированных МТ вычисление однозначно определяется входом. В сучае НМТобъединение цепей, соответствующих вычислениям на входе w, представляетсобой ориентированное (от корня) дерево с корнем C1 = q1 w.Распознавание языков. Пусть A — конечный алфавит. Через Aω обозначим множество всех слов (конечных последовательностей) в алфавите A.Через ||w|| обозначим длину слова w, определяемую, как число букв в w. Произвольное подмножество L ⊆ Aω называется языком в алфавите A.
Говорят,20что МТ (НМТ) M с двумя заключительными состояниями (принимающим иотвергающим) распознает язык L, если, для всякого слова w ∈ Aω принимающее вычисление M на входе w существует тогда и только тогда, когдаw ∈ L. В случае, когда w 6∈ L, все вычисления либо бесконечны, либо являются отвергающими. Говорят, что МТ (НМТ) M распознает язык L заполиномиальное время, если она распознает L и существует полином p такой, что для всех слов w ∈ L существует принимающее вычисление длины,не превышающей p(||w||).Через P обозначим класс языков, распознаваемых МТ за полиномиальноевремя. Через П обозначим множество отображений вида f : Aω → Aω , вычисляемых МТ за полиномиальное время.
Пусть L и K — языки. Говорят,что L (полиномиально) сводится к K (обозначение L ≺ K), если существуетфункция f ∈ П такая, что f (w) ∈ K ⇔ w ∈ L.Языки L (полиномиально) эквивалентны K, если K ≺ L и L ≺ K. Классязыков, распознаваемых НМТ за полиномиальное время, обозначается через NP. Язык L называется NP-полным, если1) L ∈ NP.2) K ∈ NP ⇒ K ≺ L.Справедливы следующие простые утверждения.Утверждение 1. Если K ∈ P и L ≺ K, то L ∈ P.Утверждение 2.
P ⊆ NP.Утверждение 3. Либо все NP-полные языки принадлежат P, либо ниодин из них не принадлежит P. Первое имеет место тогда и только тогда,когда P=NP.Утверждение 4. Если L ≺ K и K ≺ H, то L ≺ H.Язык ВЫПОЛНИМОСТЬ (короче, ВЫП) состоит из слов в алфавите A ={(, ), &, ∨, ¬, xi , i = 1, 2, ...}, представляющих собой выполнимые КНФ, т.е.КНФ, не равные тождественно 0.Теорема.(Ст.Кук) Если L ∈ NP, то L ≺ В Ы П .Доказательство. Поскольку L ∈ NP, то существует НМТ, распознающая язык L за полиномиальное время. Пусть полином p(x) и НМТ M таковы,что M распознает L и tM (w) ≤ p(||w||) для любого слова w ∈ L. Мы укажемспособ построения по произвольному слову w КНФ A(w) = A(w, M, p), выполнимой тогда и только тогда, когда w ∈ L.
Тем самым будет указано отображение f : L → В Ы П , удовлетворяющее условию f (w) ∈ L ⇔ A(w) ∈ В Ы П .Принадлежность построенного отображения f классу П легко проверяется.Занумеруем ячейки односторонней ленты НМТ M слева направо натуральными числами. Пусть Σ = {a1 , a2 , ..., al } — алфавит ленты НМТ M ,{q1 , q2 , ..., qr } — множество состояний НМТ, w ∈ Σ — произвольное слово21длины n. Положим T = p(n). Заметим, что если МТ заканчивает работу неболее чем за p(n) тактов, то ячейки ленты с номерами большими, чем T непосещаются головкой.Введем переменнные, от которых будет зависеть строящаяся КНФ A(w).iiPs,t, где 1 ≤ i ≤ l; 1 ≤ s, t ≤ T .
Переменная Ps,tистинна тогда и толькотогда, когда ячейка с номером s на шаге t содержит символ aiQjt , где 1 ≤ j ≤ r; 1 ≤ t ≤ T . Переменная Qjt истинна тогда и толькотогда, когда на шаге t НМТ находится в состоянии qj .Ss,t , где 1 ≤ s, t ≤ T . Переменная Ss,t истинна тогда и только тогда, когдана шаге t ячейка с номером s обозревается головкой.КНФ A(w) является конъюнкцией B&C&D&E&F &G, образованной следующим образом.B утверждает, что на каждом шаге t обозревается одна и только однаячейка. B является конъюнкцией B1 &B2 &...&BT , где Bt утверждает, что нашаге t обозревается одна и только одна ячейка³Bt = S1,t_S2,t_..._´ST,t ∧"V1≤i<j≤T(S i,t_#S j,t ) .Для 1 ≤ t ≤ T формула Cs,t утверждает, что на шаге t в ячейке s находится один и только один символ, а C является конъюнкцией всех такихCs,t .Формула D утверждает, что для каждого t НМТ находится ровно в одномсостоянии.
Формулы C и D строятся аналогично B.Формула E утверждает, что выполнены начальные условия.i1i2in11E = Q11 &S1,1 &P1,1&P2,1&...&Pn,1&Pn+1,1&...&PT,1,где w = ai1 ai2 ...ain — входное слово, q1 — начальное состояние и a1 — пустойсимвол.Формула F утверждает, что для каждого t преобразование слова на ленте, сдвиг головки и изменение состояния осуществляются в соответствии спрограммой НМТ. Если же ячейка не обозревается, то содержимое ее не изменяется.
F представляет собой конъюнкцию формул Fs,t по всем s, t. ФормулаFs,t утверждает:1) если на шаге t ячейка с номером s не обозревается на шаге t, то символ,находящийся в ней, не изменяется;2) если же s-я ячейка обозревается на шаге t, то изменения состояния исимвола в обозреваемой ячейке, а также сдвиг головки производятся в соответствии с программой НМТ по символу, находящемуся в s-й ячейке исостоянию НМТ.22Пусть Rs,t,i,j означает следующее: при условии, что на шаге t обозреваетсяячейка s, из того, что в обозреваемой ячейке ленты записан символ ai иНМТ находится в состоянии qj , следует, что НМТ действует в соответствиихотя бы с одной из команд, начинающихся с пары ai qj . Пусть, например, впрограмме НМТ присутствуют две команды с началом ai , qj : ai qj → ai1 qj1 Lи ai qj → ai2 qj2 R.
Тогда высказывание Rs,t,i,j имеет следующий вид:i1i212i∨ Qjt ∨ &Ps,t+1&Qjt+1&Ss−1,t+1 ∨ Ps,t+1&Qjt+1&Ss+1,t+1 .Rs,t,i,j = Ps,tВысказывание Fs,t имеет вид·Fs,t = S s,t &V1≤i≤li(Ps,t_¸_i)Ps,t+1"Ss,t &W#W1≤i≤l 1≤j≤rRs,t,i,jЗаметим, что формулы для Rs,t,i,j и Fs,t не являются КНФ. Однако каждуюиз них можно представить, например, совершенной КНФ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
