А.А. Сапоженко - Некоторые вопросы сложности алгоритмов, страница 4

Поэтому значение функции ϕ не может быть определенным. В самомKделе, значение пометки “0"противоречит тому, что K ∈ Df∪M , а значение “1— тому, что K ∈/ Dh∪M.2KСписок литературы[1] Ю.И.Журавлев, Теоретико-множественные методы в алгебре логики// В сб.

Проблемы кибернетики, М.: Наука, Вып.8, 1962, С. 5–44.[2] Ю.И.Журавлев, Избранные научные труды, М. 1998, 417 с.[3] А.А.Сапоженко, Дизюнктивные нормальные формы, Издательство МГУ, 1975, 90 с.114Теорема КукаВведение. В параграфе доказывается теорема Кука. Центральными понятиями являются (полиномиальная) сводимостьязыков, детерминированные и недетерминированные машины Тьюринга, классы P и N P , N P -полнота.

При изложениииспользовались источники [1], [2] и [3].Существует большой класс вычислительных задач, заключающийся в распознавании тех или иных свойств графов, целыхчисел, массивов целых чисел (векторов, матриц и т.п.), конечных множеств, булевых формул и др. Посредством кодированиятаких объектов множествами слов эти задачи могут быть превращены в задачи распознавания языков. Тем самым вопрос осложности самых разнообразных вычислительных задач сводится к вопросу о сложности распознавания языков.Принято считать, что задача решается эффективно, если существует алгоритм ее решения со временем работы, котороеограничено полиномом от размера входных данных. Впервые эту рабочую гипотезу выдвинул и стал защищать ДжекЭдмондс [4].

Теорема Ст. Кука и понятие полиномиальной сводимости позволяют доказать, что большой класс (т.н. N P полных) задач, ни для одной из которых пока (к 2001г.) не удалось найти полиномиального алгоритма, эквивалентны междусобой в том смысле, что либо каждая из них решается эффективно, либо ни одна из них такого решения не имеет.Определения. Термин “машина Тьюринга"(сокращенно МТ) употребляется здесь для одноленточных детерминированных машин, (см., например, [5]).

Некоторое (непринципиальное) отличие состоит в том, что мы рассматриваем МТ содносторонней лентой, бесконечной вправо. Алфавит ленты МТ обозначим через A, а множество состояний — через Q.Алфавиты 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 . Этоозначает, что в первых m ячейках ленты нет пустых символов, а все остальные ячейки содержат символ a1 .

Пусть далеетакте t МТ находится в состоянии qj , а головка обозревает ячейку с номером k. Конфигурацией (мгновенным описанием),соответствующей этому такту t, называется слово вида Ct = b1 b2 . . . bk−1 , qj bk . . . bm . Конфигурация, соответствующаяпервому такту, называется начальной, а последнему (если МТ останавливается), — заключительной. Вычислением МТ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 , ..., в которой C1 = q1 w, а Ct+1 получается из Ct спомощью одной из команд, соответствующих паре a(t)q(t), где q(t) — символ состояния, входящий в Ct , а a(t) — буква изCt , стоящая справа от q(t).

Всякое вычисление можно изобразить ориентированной цепью, вершинами которой являютсяконфигурации, а каждая дуга соединяет две последовательные вершины. В случае детерминированных МТ вычисление однозначно определяется входом. В случае НМТ объединение цепей, соответствующих вычислениям на входе w, представляетсобой ориентированное (от корня) дерево с корнем C1 = q1 w.Распознавание языков. Пусть A — конечный алфавит. Через Aω обозначим множество всех слов (конечных последовательностей) в алфавите A. Через ||w|| обозначим длину слова w, определяемую как число букв в w. Произвольноеподмножество L ⊆ Aω называется языком в алфавите A.

Говорят, что МТ (НМТ) M с двумя заключительными состояниями (принимающим и отвергающим) распознает язык L, если для всякого слова w ∈ Aω принимающее вычисление M навходе w существует тогда и только тогда, когда w ∈ L. В случае, когда w 6∈ L, каждое вычисление либо бесконечно, либо12является отвергающим. Говорят, что МТ (НМТ) 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 называется N P -полным, если1) L ∈ NP.2) K ∈ NP ⇒ K ≺ L.Справедливы следующие простые утверждения.Утверждение 1. Если L ≺ K и K ≺ H, то L ≺ H.Утверждение 2. Если K ∈ P и L ≺ K, то L ∈ P.Утверждение 3. P ⊆ NP.Утверждение 4.

Либо все N P -полные языки принадлежат P, либо ни один из них не принадлежит P. Первое имеетместо тогда и только тогда, когда P=NP.Язык ВЫПОЛНИМОСТЬ (короче, ВЫП) состоит из слов в алфавите A = {(, ), &, ∨, ¬, xi , i = 1, 2, ...}, представляющихсобой выполнимые КНФ, т.е. КНФ, не равные тождественно 0.Теорема (S.A.Cook) Если 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 ∈ Σ — произвольное слово длины n. ПоложимT = p(n). Заметим, что если МТ заканчивает работу не более чем за p(n) тактов, то ячейки ленты с номерами большими,чем T не посещаются головкой.Введем переменнные, от которых будет зависеть строящаяся КНФ A(w).iiPs,t, где 1 ≤ i ≤ l; 1 ≤ s, t ≤ T . Переменная Ps,tравна 1 тогда и только тогда, когда ячейка с номером s на шаге tсодержит символ aiQjt , где 1 ≤ j ≤ r; 1 ≤ t ≤ T .

Переменная Qjt равна 1 тогда и только тогда, когда на шаге t НМТ находится в состоянииqj .Ss,t , где 1 ≤ s, t ≤ T . Переменная Ss,t равна 1 тогда и только тогда, когда на шаге t ячейка с номером s обозреваетсяголовкой.КНФ A(w) является конъюнкцией B&C&D&E&F &G, образованной следующим образом.B утверждает, что на каждом шаге t обозревается одна и только одна ячейка. B является конъюнкцией B1 &B2 &...&BT ,где Bt утверждает, что на шаге t обозревается одна и только одна ячейка:V __ __Bt = S1,t S2,t ... ST,t ∧(S i,t S j,t ) .1≤i<j≤TДля 1 ≤ s, t ≤ T формула Cs,t утверждает, что на шаге t в ячейке s находится один и только один символ, а C являетсяконъюнкцией всех таких Cs,t .Формула D утверждает, что для каждого t НМТ находится ровно в одном состоянии.