Труднорешаемые проблемы. 
Сложность вычислений

§ 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,10 1000(1,10,1111)(1,11,1010)(10,11,1100)(10,100,10 100)(11,100,10 010).

Далее описанная версия алгоритма будет реализована на многоленточной машине Тьюринга за 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. С = 1 тогда и только тогда, когда i-я клетка ленты машины M содержит символ X j в момент времени t, где 1 i p (n), 1 j m ,
• 0 t p (n).
• 2. S = 1 тогда и только тогда, когда M в момент времени t находится в состоянии q k, где
• 1 k s, 0 t p (n) .
• 3. H = 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 0 A1… A p (n) утверждает, что в каждый момент времени машина M обозревает в точности одну клетку, соответственно At утверждает, что в момент времени t обозревается точно одна клетка, где.

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

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

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

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

0 t p (n).

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

4. D = П ((С С) + H) утверждает, что.

i, j, t.

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

(С С) + H.

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

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

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

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

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

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

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

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

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

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

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

^{n i p (n)}

• (соответствует в алфавите X₁). Формула F имеет длину O (p (n)).
• 7. G = S утверждает, что M в конце концов приходит в заключительное состояние qs.

Булева формула ₀ есть произведение 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, S, H, на котором ₀ истинно. Обратно, по 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.