Сложность вычислений

Имитируется работа универсальной машины U на входе (M,).

Если (M,) L _u, т.е. M не допускает вход , то M' прекращает работу, не допуская свой вход x.

Если (M,) L _u, т.е. M допускает , то далее M' имитирует работу машины M_L на входе x и допускает, так как xL и M_L допускает язык L.

Таким образом, для рассматриваемого свойства , где , L_u < L _, следовательно, язык L неразрешим.

b) Допустим, что . Рассмотрим , дополнение свойства , т.е. множество РП-языков, не обладающих свойством . Свойство содержит , так что как в части a) можно доказать неразрешимость языка L . Поскольку язык L есть множество кодом машин, не допускающих свойство , то L = L . Если предположить, что язык L разрешимый, то по теореме Поста, его дополнение - рекурсивный язык, что не верно.

Неразрешимые проблемы, связанные с языками машин Тьюринга:

Пуст ли язык, допускаемый машиной Тьюринга?

Конечен ли язык, допускаемый машиной Тьюринга?

Регулярен ли язык, допускаемый машиной Тьюринга?

Контекстно-свободен язык, допускаемый машиной Тьюринга?

Разрешимые (тривиальные) проблемы, связанные с языками машины Тьюринга:

Содержит ли машина Тьюринга данное число состояний?

Существует ли вход, допускаемый машиной Тьюринга за данное число переходов?

Тема 3. Труднорешаемые проблемы

§1. Классы P и NP

§2. Проблемы, решаемые за полиномиальное время

2.1 Алгоритм Крускала

2.2 Сортировки

§3. Полиномиальное сведение

§4. NP - полные проблемы

4.1 Проблема выполнимости булевой функции (ВЫП)

4.2 NP - полнота проблемы выполнимости КНФ (КНФ)

4.3 NP - полнота проблемы выполнимости 3-КНФ (3-КНФ)

4.4 Проблемы, к которым сводится проблема 3-КНФ:

Проблема независимого множества (НМ)

Проблема узельного покрытия (УП)

Проблема ориентированного гамильтонова цикла (ОГЦ)

Проблемы, к которым сводится проблема ОГЦ:

Проблема неориентированного гамильтонова цикла (НГЦ)

Проблема коммивояжера (ПК).

Самостоятельные занятия

[5], раздел 2.

[1], глава 10.

Машина Тьюринга M имеет временную сложность T(n), если на входе длины n машина M делает не более T(n) переходов и останавливается независимо от того, допущен вход или нет. Язык L принадлежит классу P, когда для некоторой машины M с временной сложностью T(n) = p (n), где p (n) - полином, L = L(M). Напомним, что в данной ситуации нет разницы между языками, допускаемыми и распознаваемыми за полиномиальное время.

Пример P - проблемы: алгоритм Крускала.

Проблема построения остовного дерева минимального веса связного неориентированного графа решается при помощи алгоритмов Крускала и Прима. Каждый из них реализуется за полиномиальное время. Оба алгоритма используют принцип “жадной” стратегии, выбирая на каждом шаге “локально наилучший” вариант. На вход вычисляющей машины подается граф, представляемый своими вершинами и ребрами. Каждому ребру приписан целочисленный вес. Остовное дерево - это связный подграф, не имеющий циклов, содержащий все вершины графа. Остовное дерево минимального веса (ОДМВ) - это дерево наименьшего веса среди остовных деревьев графа.

Построение алгоритма Крускала:

Базис. Вначале каждая вершина есть компонента связности.

Индукционный шаг. Среди еще не выбранных ребер рассматриваем ребро минимального веса. Если связываемые этим ребром вершины принадлежат разным компонентам связности, то

ребро добавляется в остовное дерево;

связанные этим ребром компоненты связности объединяются.

В противном случае ребро отбрасывается. Выбор заканчивается, если выбраны все ребра, или когда число ребер остовного дерева не станет равным V - 1.

Лемма 1. Пусть G = (V, E) - связный неориентированный граф; S = (V,T) - его остовное дерево. Тогда a) v₁, v₂ V ! v₁ v₂ (путь в S).

Если к дереву S добавить ребро (v₁,v₂) E \ T, то возникнет точно один цикл.

Доказательство. a) В противном случае S содержит цикл, что невозможно. b) В противном случае в S уже был цикл, что невозможно.

Лемма 2. Пусть G = (V,E) - связный неориентированный граф, ребрам которого приписаны целочисленный вес f : E N.

Если {(V₁, T₁), … , (V_k , T_k)}- лес, где V = V_i , T = T_i (k > 1);

i=1..k i=1..k

e = (v, w) E \ T - ребро наименьшего веса в E \ T, где v V₁, w V₁.

Тогда найдется остовное дерево, содержащее T{e}, веса, меньшего веса любого остовного дерева, содержащего T.

Доказательство. Допустим, что S' = (V, T' ) - остовное дерево графа G, содержащее T и не содержащее e, наименьшего веса среди остовных деревьев, содержащих T{e}. По лемме 1 добавление к S' ребра e образует цикл. Этот цикл будет содержать ребро e' = (v', w' ) e, где

v' V₁, w' V₁. По условие f (e) f (e' ).

Рассмотрим подграф S, образованный удалением e' из S' и добавлением в S' ребра e. В S нет циклов, поскольку единственный цикл S' был разорван удалением ребра e'. Граф S связный, так как вершины v' и w ' остались соединенными другим путем цикла в S' . Таким образом, S - остовное дерево, содержащее T и e, и f(S) f(S' ), что противоречит допущению минимальности дерева S'.

Теорема. Алгоритм Крускала строит ОДНB для связного графа G=(V,E).

Время работы алгоритма не более O(e (e+m)).

Доказательство. Корректность алгоритма следует из леммы 2.

Номер компонента каждого узла (вершины) хранится в некоторой таблице. Выбор ребра наименьшего веса среди оставшихся занимает время O(e), а поиск компонент, в которых находятся вершины этого ребра - O(m). Если вершины принадлежат разным компонентам, на просмотр таблицы для объединения всех узлов с соответствующими номерами нужно время - O(m). Таким образом, общее время работы алгоритма - O(e(e+m)). Это время полиномиально зависит от “размера” входных данных, т.е. m +e.

Для реализации решения проблемы ОДМB на машине Тьюринга потребуются уточнения как постановки задачи, так и времени решения.

- Проблема поиска ОДМВ для реализации на машине Тьюринга может быть сформулирована так: “Для связного графа G и предельного числа W выяснить, имеет ли G остовное дерево с весом не более W ?”

- Поскольку входом машины Тьюринга является слово в некотором конечном алфавите, поэтому объекты входа алгоритма Крускала должны быть закодированы. Так что полученная цепочка превысит предполагаемый “размер” входа на логарифмический сомножитель от размера входных данных. Таким образом, все, что делается за полиномиальное время с использованием одной меры, можно сделать за полиномиальное время, используя другую меру.

Пример. Рассмотрим кодирование входа проблемы ОДМВ в алфавите, содержащем символы: 1,0, (,) , “,” .

Вершины графа обозначим числами 1,…,m.

В начало кода поместим значения m и предельного веса W в двоичной системе счисления, разделенные запятой.

Для ребра (i,j) веса w код записывается в виде ( i, j, w), где числа заданы в двоичной системе.

Для графа, изображенного на рис. 10.1 с W=40, код имеет вид:

100,101000(1,10,1111)(1,11,1010)(10,11,1100)(10,100,10100)(11,100,10010).



Далее описанная версия алгоритма будет реализована на многоленточной машине Тьюринга за O(n²) шагов, где n = m+e:

На первой ленте которой будем хранить информацию об узлах и текущих номерах компонентов, их содержащих.

Вторая лента используется для хранения информации о ребре наименьшего в данный момент веса среди ребер, не помеченных как “использованные”. Поиск непомеченного ребра наименьшего веса требует времени O(n), поскольку каждое ребро просматривается только один раз, и сравнить вес можно, просматривая код входной цепочки.

3. Если ребро на некотором этапе выбрано, то соответствующие вершины помещаются на третью ленту. Чтобы установить компоненты этих двух узлов, надо просмотреть таблицу узлов и компонентов. Это потребует O(n) времени.

4. Четвертая лента может хранить информацию об объединяемых компонентах i и j. В этом случае просматривается таблица узлов и компонентов, и для каждого узла из компонента i номер компонента меняется на j. Эта процедура требует O(n) времени.

Таким образом, каждый этап работы алгоритма на многоленточной машине Тьюринга выполняется за время O(n). Число этапов e не превышает n, то время полной работы алгоритма равно O(n²). Для одноленточной машины Тьюринга на это потребуется O(n⁴) шагов.

Реализация проблемы ОДМВ (“имеет ли граф G ОДМВ с весом, не более W ?”) принадлежит классу P.

Полиномиальная сводимость в классе P

Дадим определение полиномиальной сводимости в терминах языков. Язык L₁ сводится за полиномиальное время к языку L₂ : L_{1 P} L ₂ , если существует функция f: {0,1}^* {0,1}^* , вычислимая за полиномиальное время, такая, что для любого

x {0,1}^*, x L₁ f(x) L₂.

Лемма. Если язык L₁ {0,1}^* сводится за полиномиальное время к языку

L₂ {0,1}^* и L₂ P, то L₁ P.

Доказательство. Пусть M₂ - машина, распознающая язык L₂ за полиномиальное время, F - сводящая машина, вычисляющая на входе x за полиномиальное время значение функции f(x). Построим машину M₁ , разрешающую за полиномиальное время язык L₁. Ответить на вопрос о принадлежности x языку L₁ можно, ответив на вопрос о принадлежности f(x) языку L₂ . Т.е. машина M₁ получается композицией машин F и M₂.

Очевидно, что время работы машины M₁ есть O(n^k + (cn ^k) ^j ) , где n - длина входа x.

NP - полнота и сводимость

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

Понятие полиномиальной сводимости позволяет придать точный смысл тому, что одна проблема не менее сложна, чем другая.

Язык L {0,1}^* называется NP - полным, если

1) L NP и

для любого L' NP : L' _P L .

Теорема. Если некоторая NP - полная задача разрешима за полиномиальное время, то P = NP. Если в классе NP существует задача, не разрешимая за полиномиальное время, то все NP - полные задачи не разрешимы за полиномиальное время.

Доказательство. Пусть L - NP - полный язык разрешимый за полиномиальное время. По свойству 2, для любого языка L' NP : L' _P L .

Тогда по лемме, L' P, так что P = NP.

Если некоторый язык L' NP не разрешим за полиномиальное время, и так как любой язык из класса NP полиномиально сводим к NP - полному языку L, то L не разрешим за полиномиальное время. Иначе по первой части теоремы, L' разрешим за полиномиальное время, что противоречит условию.

Таким образом, гипотеза P NP означает, что NP - полные задачи не могут быть решены за полиномиальное время на детерминированной машине Тьюринга.

Проблема выполнимости

Первой NP - полной проблемой будет проблема выполнимости булевых формул (ВЫП). Это составит содержание теоремы Кука.

Алфавит булевых формул содержит пропозициональные переменные, символы операций: &, , , символы 1, 0, вспомогательные символы: ( , ). Определение булевой формулы известно из математической логики. Формула выполнима, если найдется набор 0-1-значений переменных, на котором формула принимает значение 1.

Представим пропозициональные буквы в виде натуральных чисел, символ & как , символ как +, символы: , 1, 0, скобки - сохраним без изменения. Так что булева формула примет вид цепочки, составленной из символов натуральных чисел (которые мы представим в двоичной системе) и символов: , + , 0, 1, (, ).

Предложение. Язык ВЫП, состоящиий из цепочек, представляющих выполнимые булевы функции, принадлежит классу NP.

Доказательство. Недетерминированная машина Тьюринга, распознающая язык ВЫП, “угадывает” выполняющий набор T 0-1-значений пропозициональных переменных во входной цепочке ₀, представляю щей булеву формулу, если такой набор существует. Угадывание есть параллельная работа на всех ветвях дерева вычислений недетерминированной машины. После подстановки значений 0-1 вместо пропозициональных переменных необходимо осуществить сдвиги, чтобы убрать

освободившиеся ячейки, занятые перед этим двоичными представлениями натуральных чисел, представляющих пропозициональные переменные. Если ₀ (T) = 1, то машина допускает вход ₀, даже если другие ветви не приводят в допускающее состояние, как следует из определения недетерминированной машины Тьюринга.

Значение формулы с помощью многоленточной недетерминированной машины Тьюринга можно осуществит за 0(n²) переходов. Таким образом, процесс распознавания ВЫП многоленточной машиной Тьюринга занимает время O(n²), поэтому язык ВЫПNP.

Теорема Кука. Проблема ВЫП NP - полна.

Доказательство. Первая часть теоремы была доказана в предложении.

Покажем, что произвольный язык L из NP полиномиально сводится к языку ВЫП. Для языка L NP найдется недетерминированная одноленточная машина Тьюринга, обрабатывающая вход длины n не более, чем за p(n) шагов вдоль любой ветви. По M, будем строить булеву формулу ₀, выполнимую тогда и только тогда, когда M допускает . Сводящий алгоритм должен иметь полиномиальную сложность. Пусть M имеет состояния q₁, q₂ ,…,q _s и ленточные символы X₁, X ₂,…,X _m. Если M допускает вход длины n, то делает это не более, чем за p(n) шагов. В этом случае найдется последовательность МО Q₀, Q₁,…,Q _q, где Q₀ - начальное, а Q_q - заключительное (допускающее) МО, Q_{i -1} + Q _i для 1 i q , q p(n), и ни одно МО не занимает на ленте более p(n) клеток.

Булева функция ₀, которую мы собираемся построить, должна моделировать последовательность МО, проходимых машиной, и принимает значение 1, когда моделируемая последовательность МО приводит к допусканию входа. Другими словами, булева функция выполнима, когда M допускает вход . В качестве пропозициональных переменных берем следующие предикаты:

1. С< i, j, t > = 1 тогда и только тогда, когда i-я клетка ленты машины M содержит символ X _j в момент времени t, где 1 i p(n), 1 j m ,

0 t p (n).

2. S< k, t > = 1 тогда и только тогда, когда M в момент времени t находится в состоянии q _k, где

1 k s , 0 t p(n) .

3. H< i, t > = 1 тогда и только тогда, когда головка в момент времени t обозревает i-ю клетку, где

1 i p(n) , 0 t p(n).

Пропозициональных переменных всего O(p(n)²), их представление двоичными числами займет не более c log n разрядов, где c - константа, зависящая от p. Из этих пропозициональных переменных построим функцию ₀, следуя структуре последовательности МО Q₀, Q₁,…,Q _q.

Введем предикат U(x₁,…,x _r ), принимающий значение 1, когда в точности один из аргументов x₁,…,x_r принимает значение 1. Очевидно, что

U (x ₁,…,x _r) = (x ₁ +…+ x _r ) ( П (x _i + x _j )),

i j

где первый множитель означает, что по крайней мере одна из переменных x_i истинна, остальные r (r-1)/2 сомножителя утверждают, что никакие две переменные не являются одновременно истинными. Длина цепочки, представляющей предикат U (x₁,…,x _r ), порядка O(r²).

Если машина M допускает вход , то найдется последовательность МО Q₀, Q₁,…,Q_q, проходимых машиной в ходе обработки цепочки .

Поскольку сложность вычислений машины M на входе длины n не превосходит p(n), для удобства будем считать, что машина делает точно p(n) шагов, допуская вход , а все МО содержат p(n) клеток, в противном случае этого легко добиться, добавляя не меняющие последнее МО переходы, а также дополняя МО пустыми символами.

Построим семь формул, которые будут утверждать, что Q₀, Q₁,…,Q _{p (n)} - допускающая последовательность, что фактически означает следующее:

в каждом МО головка обозревает одну клетку;

в каждом МО в каждой клетке записан один символ;

каждое МО содержит одно состояние;

при переходе Q _i-1 + Q _i (1 i p(n)) изменяется разве что содержимое обозреваемой ячейки;

переход Q _i-1 + Q _i (1 i p(n)) осуществляется в соответствии с функцией переходов машины M;

Q₀ - начальное МО;

Q _{p( n)} - заключительное МО.

Построим булевы формулы, интерпретируемые как утверждения 1-7:

1. A = A ₀ A₁…A _{p (n)} утверждает, что в каждый момент времени машина M обозревает в точности одну клетку, соответственно A_t утверждает, что в момент времени t обозревается точно одна клетка, где

A_t = U (H< 1, t >, …,H< p(n), t >). Формула A имеет длину O(p³(n)).

B = П B _{i t} утверждает, что каждая клетка в каждый момент времени ^{i, t} содержит точно один символ, соответственно B _{i t} утверждает, что i-я клетка в момент времени t содержит точно один символ, где

B _{i t} = U ( C < i, 1, t>, …, C < i, m, t >). Формула B имеет длину O(p²(n)).

3. С = П U (S < 1, t >,…, S <s, t >) утверждает, что в каждый момент

0 t p( n)

времени машина M находится точно в одном состоянии. Формула С имеем длину O( p(n)).

4. D = П ( (С < i, j, t > С < i, j, t + 1 >) + H < i, t > ) утверждает, что

i,j,t

в любой момент времени t можно изменить содержимое не более, чем одной ячейки, а формула

(С < i, j, t > С < i, j, t + 1 >) + H < i, t >

утверждает, что либо a) в момент времени t головка обозревает ячейку i, либо b) в момент времени t+1 в клетке i записан символ j тогда и только тогда, когда он был записан там в момент времени t.

Длина формулы D равна O(p²(n)).

5. E = П E_{i j k t} утверждает, что очередное МО получается из предыдущего ^{i , j, k, t} одним переходом, согласно функции переходов машины M, где E_{i j k t} означает одно из следующих утверждений:

в момент времени t клетка i не содержит символа j;

в момент времени t головка не обозревает клетку i;

в момент времени t машина M не нааходится в состоянии k;

очередное МО машины M получается из предыдущего переходом, задаваемым функцией .

E _{i j k t} = C < i, j, k > + H< i, t > + S< k, t > + ( C<i, j_l , t+1 >

S< k_l , t+1> H< i_l , t+1>), i

где l пробегает по всем шагам машины M, когда M обозревает символ X_j в состоянии q_k. Т.е. для каждой тройки < q, X, d > из (q _k, X_j) существует одно значение l, для которого Xj_l = X, q _kl = q и число i_l равно i -1, i или i+1 в зависимости от значения d, равного соответственно L, S, R. Поскольку машина M недетерминированная, таких троек < q, X, d > может быть несколько, но их конечное число, таким образом E_{i j k t} имеет ограниченную длину, не зависящую от n. Формула E имеет длину O(p²(n)).

6. F = S< 1, 0 > H< 1,0 > П C< i, j _i , 0 > П C< i, 1, 0 >, где S< 1, 0 > утверждает, ^{1 i n n i p(n)} что в момент t =0 машина M находится в начальном состоянии q₁; H< 1, 0 > утверждает, что M в момент t=0 обозревает самую левую ячейку ленты; П C< i, j _i , 0 > утверждает, что первые n клеток вначале содержат входную цепочку ;^{1 i n} П C< i, 1, 0 > утверждает, что остальные клетки вначале пусты.

^{n i p( n)}

( соответствует в алфавите X₁). Формула F имеет длину O(p(n)).

7. G = S < s, p(n) > утверждает, что M в конце концов приходит в заключительное состояние q_s.

Булева формула ₀ есть произведение ABCDEFG. Каждый сомножитель содержит не более, чем O(p³(n)) символов, так что сама формула ₀ состоит не более, чем из O(p³(n)) символов. Представляя пропозициональные переменные цепочками длины O(log n), получим в качестве верхней границы длины ₀ величину порядка O(p³(n) log n), что не превосходит cnp³(n), где c - некоторая константа. Таким образом, формулу ₀ можно построить за время, пропорциональное ее длине.

По данной допускающей последовательности МО Q ₀, Q ₁,…,Q _q можно, очевидно найти 0-1-набор для пропозициональных переменных C< i, j, t>, S< k, t >, H< i, t >, на котором ₀ истинно. Обратно, по 0-1-набору, обращающем ₀ можно найти допускающую последовательность МО. Таким образом, формула ₀ выполнима тогда и только тогда, когда M допускает цепочку . Тем самым построен алгоритм полиномиальной сложности, сводящий язык L NP к языку ВЫП. Тем самым задача ВЫП NP-полна.

Следствие. Задача выполнимости булевых формул, находящихся в конъюнктивной нормальной форме (ВКНФ), NP - полна.

Говорят, что формула находится в k-конъюнктивной нормальной форме (k-КНФ), если она есть произведение сумм, состоящих не более чем из k литералов. Для k=1, 2 известны детерминированные полиномиальной сложности алгоритмы, распознающие языки 1-КНФ и 2-КНФ.

Рассматриваемая ниже задача 3-выполнимости, как и задачи ВЫП и ВКНФ, представляют интерес не только сами по себе, но и в связи с тем, что они полиномиально сводятся еще к ряду задач, откуда следует NP- полнота последних.

Теорема. Задача 3-выполнимости NP-полна.

Доказательство. Покажем, что выполнимость формул в КНФ полиномиально сводится к 3-выполнимости. Заменим каждый член (x₁ + x₂+…+x _k), на (x ₁ + x ₂ + y ₁)(x ₃ + y ₁ + y ₂)( x ₄ + y ₂ + y ₃)…(x _{k -1} + x _k+ y_{k -3}) (k 4), где y ₁, y ₂,…,y _k-3 - новые переменные.

Присвоить значения новым переменным так, чтобы вновь полученная формула приняла значение 1, можно тогда и только тогда, когда исходная формула принимает значение 1.

Длина формулы, получаемой в результате описанной замены, превосходит длину исходной формулы не более, чем в постоянное число раз. Таким образом, по данной формуле E в КНФ можно найти формулу E' в 3-КНФ, выполнимую тогда и только тогда, когда выполнима исходная формула. Причем, E' находится за время, пропорциональное длине формулы E.

Тема 4. Другие сложностные классы

§1. Дополнение языков из NP

1.1 Класс языков co-NP

1.2 Классы PS и NPS

1.3 PS - полнота. Булевы фукнкции с кванторами (КБФ)

§2. Классы языков, основанных на рандомизации

2.1 Быстрая сортировка как пример рандомизированного алгоритма

2.2 Язык рандомизированной машины Тьюринга

2.3 Класс RP

2.4 Класс ZPP

Самостоятельные занятия

[1], глава 11

[4], глава 10.6

Класс co-NP - дополнений языков из NP. Если P = NP, то класс co-NP равен обоим, так как класс P замкнут относительно дополнения. Однако более вероятно, что ни одна NP-полная проблема не принадлежит co-NP.

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

Рандомизированные алгоритмы, реализуемые машинами Тьюринга, использующими при вычислениях последовательность случайных чисел, и определяемые ими два класса языков - RP и ZPP. Языки класса RP (случайные полиномиальные языки) имеют алгоритм, работающий полиномиальное время, используя генератор случайных чисел. Алгоритм или подтверждает принадлежность входа языку, или отвечает “не знаю”. Кроме того, если вход на самом деле принадлежит языку, повторное применение к нему алгоритма подтвердит принадлежность с вероятностью, близкой к 1. Языки класса ZPP (безошибочные, вероятностные полиномиальные) также используют случайные числа, но алгоритм дает ответ: “да”, если вход принадлежит языку, и “нет” - в противном случае . Ожидаемое время работы алгоритма полиномиально, однако возможно, что выполнение алгоритма потребует больше времени, чем полиномиальное.

Класс co-NP

Класс языков P замкнут относительно дополнения. Пусть L P и L=L(M). Для допускания L' изменим M следующим образом: введем новое заключительное состояние q и новые переходы в q из тех состояний, в которых M останавливалась, не допуская, заключительные состояния M сделает недопускающими. Измененная машина Тьюринга допускает язык L' и время ее работы совпадает с T(M)+1. Т.е. L' P, если L P.

Hаиболее вероятно, что дополнения NP-полных проблем не принадлежат NP, поэтому в co-NP нет ни одной NP-полной проблемы.

С другой стороны, дополнения NP-полных проблем принадлежат co-NP, так что не находятся в NP.

Пример. Язык ВЫП принадлежит классу NP, его дополнение НВЫП, содержащее все невыполнимые булевы формулы и слова, не являющиеся кодами допустимых булевых формул, принадлежит co-NP. Вероятно, что НВЫП NP, но доказательство последнего утверждения равносильно проблеме P NP.

NP-полные проблемы и co-NP.

Предположим, что P NP. Допустим, что NP = co-NP. Тогда проблемы типа НВЫП можно решить за полиномиальное время на недетерминированной машине Тьюринга, но нельзя решить за полиномиальное время на детерминированной машине. Последнее противоречит допущению.

Теорема. NP = co-NP тогда и только тогда, когда существует NP-полная проблема, дополнение которой принадлежит NP.

Доказательство. Необходимость. Если NP = co-NP, то каждая NP-полная проблема L принадлежала бы как NP, так и co-NP. Но дополнение проблемы из co-NP находится в NP, поэтому дополнение L принадлежит NP.

Достаточность. Пусть R - NP-полная проблема, дополнение которой принадлежит NP. Тогда для любого языка LNP : L< _P R , L' < _P R'.

Докажем равенство классов NP и co- NP, показав их взаимное включение.

NP co-NP : Пусть LNP. Тогда L' co-NP. Применим к x L` сводящий алгоритм L' < _p R' , а результат на выходе подадим недетерминированной машине Тьюринга, вычисляющей проблему R', построенную композицию объявим машиной, вычисляющей язык L', откуда L' NP, cледовательно, L NP.

Co-NP NP. Пусть L co-NP. Тогда существует полиномиальное сведение L' к P, поскольку P является NP-полным, а L' принадлежит NP.

Это сведение является также сведением L к P'. Цепочку x L подадим на вход сводящего алгоритма, выход которого подадим недетерминированной машине, вычисляющей P', полученную композицию объявим недетерминированной машиной, вычисляющей язык L, так что L NP.

Проблемы, разрешимые в полиномиальном пространстве

Рассмотрим класс проблем, включающий классы P и NP. Этот класс определяется машинами Тьюринга с полиномиальной емкостной сложностью (время работы значения не имеет). Дальше будет показано, что классы языков PS и NPS, допускаемые соответственно детерминированными и недетерминированными машинами Тьюринга с полиномиально ограниченным объемом памяти (используемой рабочей лентой), совпадают.

В полиномиальном пространстве существуют полные проблемы P в том смысле, что все проблемы данного класса полиномиально сводимы к P. Таким образом, если P P или P NP, то все языки машин Тьюринга с полиномиально ограниченной емкостью принадлежат P или NP, соответственно. Примером такой проблемы будет язык “булевых формул с кванторами” (КБФ).

Классы PS и NPS.

Включения P PS и NP NPS очевидны. Доказав, что PS = NPS,, получим : P NP PS..

Другой интересный факт, касающийся новых классов, тот, что PS содержит только рекурсивные языки.

Теорема. Если M - машина Тьюринга с полиномиально ограниченным пространством, где p(n)- ограничивающий полином, то существует константа c, что M допускает вход длины n за O(с^{1+ p(n)} ) переходов.

Доказательство. В обосновании существования “c” используется то, что у машины Тьюринга с ограниченным пространством имеется лишь ограниченное число МО. Если t - число ленточных символов, а s - число состояний машины M, то число различных МО машины, использующей p(n) клеток, не более s p(n) t ^p(n) , т.е. можно выбрать одно из s состо- яний, поместить считывающую головку в одну из p(n) позиций и заполнить p(n) клеток любой из t ^p(n) последовательностей ленточных символов.

Положим c = s + t и вычислим бином (t + s)^{1 + p(n)} =

1 + t ^{1 + p(n)} + (1 + p(n))s t ^p(n) + …, где второе слагаемое не меньше

p(n)s t ^p(n), что доказывает, что c ^{1 + p(n)} не меньше числа возможных конфигураций M. Если машина M допускает вход длины n, то она совершает последовательность конфигураций без повторений. Следовательно, M допускает, совершив не более c ^{1 + p(n)} переходов (количество различных МО).

Теорема. Если L - язык из PS (NPS), то L допускается детерминирован- ной (недетерминированной) машиной Тьюринга с полиномиально ограниченным пространством, которая для некоторого полинома q(n) и константы “c” останавливается, сделав не более с ^{q (n)} переходов.

Доказательство. Пусть язык L допускается детерминированной машиной Тьюринга M₁ (для НМТ доказательство аналогично), имеющей полиномиальное ограничение пространства p(n). По теореме 11.3, если M₁ допускает вход w, то делает около c ^{1 + p(w )} шагов.

Построим машину M₂, имеющую две ленты. На первой ленте M₂ имитирует M₁, а на второй ведет счет шагов до c ^{1 + p(w )} и останавливается, не допуская, если это число достигнуто. Поскольку машиной M₁ используется не более p (w ) клеток, M₂ использует также не более p (w ) клеток первой ленты.

Преобразуя M₂ в одноленточную машину M₃, можно гарантировать, что M₃ использует не более 1 +p (w ) клеток и время работы O(c^{2 p(w )}).

Машина M₃ совершает не более dc ^{2 p(w )} переходов для некоторой константы d, поэтому можно выбрать q(n) = 2 p(n) + log _c d, где n - длина входа. Тогда M₃ совершает не более c^q(n) шагов. M₂ всегда останавливается, поэтому то же делает и M₃. M₁ допускает L, поэтому M₂ и M₃ допускают L. Таким образом, M₃ удовлетворяет теореме.

Теорема (Теорема Сэвича). PS = NPS.

Доказательство. Очевидно, что PS NPS , поскольку каждая ДМТ является также и НМТ. Доказываем обратное включение: NPS PS, т.е. если L допускается НМТ N с ограничением пространства p(n), где p(n)- полином, то L также допускается ДМТ D с ограничением пространства полиномом q(n). Доказательство основано на имитации НМТ N с помощью ДМТ D.

Машина D с помощью рекурсивной процедуры проверяет, что пере- ход от одной МО I к другой - J осуществляется не более, чем за m переходов. По теореме 11.3, если N допускает, то делает это в пределах c^1+p(n) шагов, где c - некоторая константа, также и m не превышает c^p(n). Получив вход w, машина D исследует тройки вида [I₀, J, m ], где I₀ - исходное МО, J - заключительное МО машины N, в котором используется не более p(n) клеток. m в каждом вызове рекурсивной процедуры уменьшается в два раза, пока не станет равным 1. Рекурсивных вызовов не более log ₂ m, так что элементов [I, J, m/2i] - log ₂ m, т.е. log ₂ c^1+p(n), или O(p(n)).

Каждый элемент вызова занимает пространство O(p(n)), для записи каждого МО требуется 1+p(n) клеток, а для записи в двоичном виде - log₂ c^1+p(n), т.е. O(p(n)) клеток.

Таким образом, D использует пространство O(p²(n)), т.е. L допускается ДМТ с полиномиально ограниченным пространством.

Проблема, полная для класса PS.

Проблема P определяется как полная для PS (PS-полная), если :

P PS.

Все языки L из PS полиномиально сводимы к P.

Теорема. Пусть P - PS-полная проблема. Тогда :

a) если P P, то P = PS;

b) если P NP, то NP = PS..

Доказательство. Докажем (a). Дано, что P - PS-полная проблема, тогда любой язык L из PS полиномиально, за время q (n), сводим к P. Пусть P P и время работы допускающей ДМТ задается полиномом p(n) .

Цепочка w принадлежит языку L тогда и только тогда, когда, используя сведение, можно получить цепочку x, принадлежащую P. Поскольку сведение занимает время q (w), цепочка x не может быть длинее, чем q (w). Принадлежность x к языку P можно проверить за время p(x), т.е. p(q (w)), полиномиальное относительно w. Следовательно, для L сушествует полиномиальный по времени алгоритм и L P. Таким образом, PS P. Обратное включение очевидно.

Доказательство (b) аналогично с заменой ДМТ на НМТ.

Примером PS-полной проблемы будет класс “булевых формул с кванторами ” (КБФ). Проблема формулируется так: имеет ли булева формула с кванторами без свободных переменных значение 1 ?

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

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

Утверждение разбито на две части : КБФ PS и каждый язык из PS полиномиально (по времени) сводим к КБФ.

Теорема. КБФ принадлежит PS.

Доказательство. Рекурсивный процесс вычисления КБФ F может быть организован с использованием магазина, хранимого на ленте машины Тьюринга, как в доказательстве теоремы Сэвича. Пусть n - длина F. Тогда для F создается запись длиной O(n), включающая саму F и пространство для записи обрабатываемых подформул F. Вычисления проводим индукцией по построению формулы F:

Пусть F = F₁ + F₂ , тогда выполняем следующее :

помещаем F₁ в ее собственную запись справа от записи F;

рекурсивно вычисляем F₁;

если значением F₁ является 1, то возвращаем 1 как значение F;

если значение F₁ есть 0, то ее запись заменяем записью F₂ и рекурсивно вычисляем F₂;

в качестве значения F возвращаем F₂.

Пусть F = x E. Тогда выполняем следующее :

подставляем вместо x значение 0 и полученную запись E₀ помещаем справа от записи F;

рекурсивно вычисляем E₀;

если значение E₀ равно 1, то возвращаем 1 как значение F;

если значение E₀ равно 0, на место E₀ помещаем запись E₁, подставляя 1 вместо x, и рекурсивно вычисляем E₁;

в качестве значения F возвращаем значение E₁.

Для остальных форм F (F₁F₂, E, x E) доказательства аналогичны. Для базисного случая, когда F- константа, она возвращается без записей на ленте

Посчитаем объем памяти (ленты). Если F - длины n, на ленте n записей, каждая длиной O(n). Поэтому объем памяти не не превышает O(n²). Таким образом, машина Тьюринга, допускающая КБФ с полиномиально ограниченным пространством. Время работы алгоритма экспоненциально относительно n.

Для сведения языка L из PS к проблеме КБФ воспользуемся идеей доказательства теоремы Кука, где использовались пропозициональные переменные y_ijA для утверждения, что в j-й позиции i-го МО находится символ A. Однако, поскольку МО экспоненциальное число, воспользуемся квантификацией, чтобы с помощью одного и того же множества переменных представлять много различных МО.

Теорема. Проблема КБФ PS-полна.

Доказательство. Пусть L - язык из PS , допускаемый недетерминированной машиной M, которая на входе длины n использует не более p(n) клеток. По теореме Сэвича существует константа “c”, для которой M допускает вход за c ^{1+ p(n)} переходов (если допускает). Опишем, как за полиномиальное время по входу w длины n построить КБФ E без свободных переменных, имеющее значение 1 тогда и только тогда, когда

w L(M).

Для записи E потребуется ввести полиномиальное число переменных y_{j A}, утверждающих, что j-я позиция представляемого МО содержит символ A - ленточный или состояние M (j может изменяться от 0 до p(n)).

Предположим, что пропозициональные переменные разных МО различны. Но поскольку разных МО полиномиальное число, общее количество пропозициональных переменных полиномиально.

Обозначим кванторную приставку (x₁x_2…x_m), где x₁, x₂,…,x_m - все пропозициональные переменны МО I как (I); аналогично для квантора всеобщности - (). КБФ примет вид :

(I₀) (I_f) (S & N & F), где

I₀ и I_f - переменные МО, представляющие начальное и допускающее М, соответственно.

S - выражение, говорящее, что I₀ является начальным МО машины M на входе w.

N - выражение, говорящее о переходах M при преобразовании I₀ к I_f.

F - выражение, говорящее, что I_f является допускающим МО.

О каждой формуле в деталях:

S - конъюнкция литералов; каждый литерал - одна из переменных МО. Литерал y_{j A} входит в I₀ , если в j-й позиции начального МО с входом w находится символ A, в противном случае в I₀ входит y_{j A}.

Таким образом, если w = a ₁a ₂…a _n , то без отрицания в МО I₀ входят

^y0q ₀ , ^y1a₁ , ^y2a₂ ,…, ^yna_n и все ^yj B для j = n+1, n+2,…, p(n),

где q₀ - начальное состояние и B = , а все остальные переменные МО I₀ - с отрицаниями.

I_f - допускающее МО, если содержит заключительное (допускающее) состояние. F - дизъюнкция переменных ^yj A, выбранных из пропозициональных переменных МО I_f , для которых A является допускающим состоянием. Позиция j произвольна.

N - строится с помощью метода, позволяющего удвоить число рассматриваемых переходов, добавив лишь O(p(n)) символов и затратив O(p(n)) времени. Равенством I = J обозначим конъюнкцию выражений

( ^yj A ^z j A ^{+ y}j A ^z j A),

где j изменяется от 0 до p(n), а A - любой ленточный символ или состояние M, МО I состоит из переменных y_{j A} и J - из переменных z _{j A}.

N_i (I, J) - означает, что переход от МО I к МО J занимает не более i переходов, обозначается I + ⁱ J, i = 1,2,4,… . В этих выражениях свободны только переменные I и J, остальные переменные связаны.

Базис. Для i = 1 выражение N_i (I, J) устанавливает, что I = J или I + ¹ J, т.е. N₁(I, J) есть дизъюнкция этих утверждений. N₁ (I, J) записывается за время O(p(n)).

Индукционный шаг. По N_i строим N_2i . Корректный способ записи N_2i состоит в том, чтобы в выражении записывать одну копию N_i , подставляя как (I, K), так и (K, J) в одно и то же выражение. Таким образом, в N_2i (I, J) используется одно подвыражение N_i (P, Q). N_2i (I, J) утверждает, что существует МО K, при котором для всех МО P и Q выполняется хотя бы одно из следующих условий :

1) (P, Q) (I, K) и (P, Q) (K, J); 2) N_i (P, Q) - истинно.

Иными словами, N_i (I, K) и N_i (K, J) истинны, а для других пар МО

(P, Q) истинность N_i (P, Q) не имеет значения. Итак, КБФ имеет вид :

N_2i (I, J) = (K)(P)(Q)(N _i (P, Q) ( (I = P & K = Q) & (K = P & J = Q))).

На запись N_2i (I, J) уходит время, необходимое для записи N _i , а также O(p(n)) для дополнительной работы.

Чтобы завершить построение N, нужно записать N_m для наименьшего m, которое является степенью 2 и не меньше c^{1+ p(n)} - максимально возможного числа переходов, совершаемых M до заключительного (допуска- ющего) состояния. Количество применений шага индукции, описанного выше, равно log₂ (c^{1+ p (n)} ), или O(p(n)). Поскольку каждое исполнение шага индукции требует O(p(n)) времени, то N строится за время O(p²(n)).

Завершение доказательства теоремы. Выше было показано, как преобразовать вход w в КБФ - (I₀) (I_f) (S & N & F) за время, полиномиальное относительно w. Было доказано, что выражения S, N, F - истинны тогда и только тогда, когда их свободные переменные представляют МО I₀ и I_f , являющиеся соответственно начальным и заключительным МО в вычислениях машины M на входе w. Таким образом, данная КБФ имеет значение 1 тогда и только тогда, когда M допускает w.

Классы языков, основанные на рандомизации

Вероятностная машина отличается от детерминированной тем, что в левой части инструкции появляется еще один символ - выходное значение датчика случайных чисел с конечным алфавитом, который на каждом шаге работы выдает свои значения равновероятно и независимо от значений, выданных на других шагах. Вероятность “p” вычисления на вероятностной машине на входе “x” результата “y” равна сумме вероятностей всех реализаций “y” на входе “x”. Говорят, что машина выдает результат “y” для входа “x” со сложностью m (временной, ленточной) и вероятностью “p”, если на входе “x” с вероятностью не меньшей p, израсходовав не более m единиц (шагов, ячеек памяти), машина останавливается с результатом “y”. Таким образом, для вероятностной машины возможно, хотя и с малой долей вероятности, получить неверный результат.

...