В.А. Носов - Основы теории алгоритмов и анализа их сложности (курс лекций), страница 17

Не нарушая общности, можно считать, что q(n)= с1 n 2( c1, c2 -константы). По определению класса NP, если вход x длины nпринимается HT, то существует слово c(x) длины не более чем q(n), такое, чтоНТ дает ответ "ДА" не более чем за q(n) шагов. Значит, общее число возможныхслов-догадок не более чем k q( n) , где k - мощность внешнего алфавита НТ.Считаем, что все догадки имеют длину q(n), в противном случае их можноподравнять.

Теперь можно представить детерминированный алгоритм решениязадачи П, который на каждом из k q( n) слов-догадок реализует 2-ю стадиюработы НТ и работает q(n) тактов. Алгоритм дает ответ "Да", если найдетсяслово-догадка, приводящая к принимающему вычислению. Время работыданного алгоритма q(n)⋅ k q( n) . Ясно, что существует подходящий полином p(n),93что сложность описанного алгоритма не превосходит O( 2 p( n) ). Теоремадоказана.Относительно класса NP следует сделать несколько замечаний.1) Класс NP один и тот же для различных вычислительных моделей,использующих недетерминированные операции.2) Класс Р замкнут относительно дополнения задач.

Для класса NP этогоутверждать нельзя. Дополнением A задачи распознавания A называют задачу, вкоторой коды задач с ответом "Да" в точности соответствуют кодам задач А,которые не имеют ответ "Да". Класс задач, являющихся дополнениями к задачамкласса NP обозначают CO- NP.94§ 15. NP -полные задачи. Теорема Кука1°. Если P ≠ NP, то задачи из NP\P являются труд- норешаемыми. Цельдальнейших результатов состоит в доказательстве того, что существуютконкретные задачи П, для которых справедливо включение П∈NP\P, если P ≠NP.

Соответствующие результаты основаны на понятии полиномиальнойсводимости задач. Пусть П1 , П2 - две задачи распознавания, задаваемые валфавитах А 1 и А 2 соответственно. Будем говорить, что задача П1полиномиально сводится к задаче П2 (Обозначение: П1 ∝ П2 ), если существуетсловарная функция f : А 1 *→ А 2 * , такая, что выполнены условия :1) f - полиномиально вычислима;2) ∀x∈ А 1 * выполнено:x - индивидуальная ⇔ f(x)∈ А 2 * - индивидуальнаязадача П2 с ответом ДАзадача П1 с ответом ДАУтверждение 1. Если выполнено П1 ∝ П2 и П2 ∈P, тоП1 ∈P.Доказательство.

Предложим полиномиальный алгоритм решения задачиП1 : x∈ П1 находим f(x)∈ П2 и применяем к f(x) полиномиальный алгоритм,существующий по условию. Если получен ответ ДА, то x имеет ответ ДА. Впротивном случае x имеет ответ НЕТ. Время работы алгоритма не превосходитp f (| x| ) + p2 ( p f (| x|)) , где p f - полином, ограничивающий время вычисленияфункции f, участвующей в сведении П1 ∝ П2 , p2 - полином, ограничивающийвремя решения задачи П2 . Утверждение доказано.Утверждение 2. Если выполнено П1 ∝ П2 и П2 ∝ П3 , то П1 ∝ П3 .Доказательство очевидно, т.к.

функция f3 ( x) = f2 ( f1 ( x)) осуществляетсведение П1 ∝ П3 , если f1, f2 дают сведения П1 ∝ П2 , П2 ∝ П3 соответственно.Определение. Задача П называется NP -полной, если выполненоа) П∈NPб) П1 ∝П для любой задачи П1 ∈NP .Задача П называется NP -трудной, если для нее выполнено условие б).Обозначим через NPC - класс NP -полных задач, а через NPH - класс NP трудных задач. Согласно определению имеем:NPC ∩ P ≠ ∅ ⇒ P = NPNPH ∩ P ≠ ∅ ⇒ P = NPNPC ∩ (NP\P) ≠ ∅ ⇒ NPC ∩ P = ∅Другими словами: Если для какой-то NP -полной задачи существуетполиномиальный разрешающий алгоритм, то и для любой задачи из класса NP95существует полиномиально разрешающий алгоритм. То же высказываниесправедливо относительно NP -трудной задачи. Если какая-то NP -полная задачане лежит в классе P, то и все NP -полные задачи не лежат в классе P.Утверждение 3.

Если задачи П1 , П2 ∈NP, П1 ∝ П2 и П1 ∈NPC, то П2 ∈NPC.Доказательство. Пусть П’∈NP - произвольная задача. Тогда поопределению П’∝ П1 . Поскольку по условию П1 ∝ П2 , то согласно утверждения 2имеем П’∝ П2 , что и доказывает данное утверждение.Отсюда получаем способ доказательства NP -полно-ты конкретных задач,используя полиномиальное сведение к ней другой NP -полной задачи.

Этот жеспособ пригоден и для доказательства NP -трудности задачи. Напомним, чтоклассы NPC и NPH определяются только выполнимостью условий а),б) для NPCи условия б) для NPH.Докажем теперь важную теорему Кука С. (1971), дающую первый примерNP -полной задачи.2°. Теорема 4. Задача проверки выполнимости произвольной КНФ является NP полной задачей.Доказательство. Пусть ВЫП - идентификатор данной задачи. Впредыдущем разделе было показано, что ВЫП∈ NP.Пусть П - произвольнаязадача из NP. Необходимо показать, что П∝ВЫП. Для этого множествоиндивидуальных задач LП с ответом ДА представим в стандартном видесоответствующей недетерминированной машиной Тьюринга (обозначение:НДМТ), работающей полиномиальное время и принимающей множество LП .Такое представление дает общую сводимость задачи, решаемой НДМТ заполиномиальное время.Пусть распознающая множество LП НДМТ имеет алфавиты А,Q ифункцию переходов (программу)δ : A × Q \ {qY , qN } → A × Q × ∆ ( ∆ ∈ {R, L, S}) , p(n) - верхняя границавремени вычисления.

Функцию f L , осуществляющую полиномиальное сведениеП∝ВЫП опишем в терминах работы НДМТ.В вычислениях участвуют ячейки ленты с номерами от - p(n) до p(n) +1 ипри этом требуется учесть не более p(n) +1 тактов работы НДМТ. Проверяющеевычисление определяется заданием в каждый момент времени содержания ячеекс указанными номерами, внутреннего состояния машины и положениясчитывающей головки.

Соответствующие вычисления опишем в виде КНФ,использующей полиномиальное число дизъюнкций. Фиксируем нумерацию валфавитах:Q : q0, q1 = qY , q2 = qN , q3,...,qrA : a0 = ∧, a1,...,avУсловимся, что фраза “в момент времени i ” означает “после выполнения i -гошага работы”. Если вычисление закончилось раньше времени p(n), токонфигурация не меняется во все моменты после остановки. В нулевой моментна ленте записано слово x в ячейках с номерами 1,... ,n. Слово-догадка w пишется96в ячейках с номерами -1,-2,... ,-|w|. Остальные ячейки пусты. Описываяпринимающее вычисление необходимо учестьа) в ячейках пишется точно один символ;б) машина находится точно в одном состоянии;в) головка может просматривать точно одну ячейку с номером от - p(n) доp(n) +1;г) машина работает по программе.Определим сначала переменные и их смысл с помощью таблицы:ПеременнаяQ(i,k)Пределы изменения индексов0 ≤ i ≤ p(n)0≤ k ≤ rH(i,j)0 ≤ i ≤ p(n)- p(n) ≤ j ≤ p(n)+1a(i,j,k)0 ≤ i ≤ p(n)- p(n) ≤ j ≤ p(n)+10≤ k ≤ vСмыслв момент времени iмашина находится всостоянии qkв момент времени iголовка просматриваетячейку с номером jв момент времени iв j-ой ячейке записан символakОписание сводящей функции f L для П ∝ ВЫП дадим в виде наборадизъюнкций, конъюнкцией которых и будет f L .

При этом выполняющий наборзначений истинности однозначно соответствует принимающему вычислению наx, стадия проверки занимает время ≤ p(n) шагов, слово-догадка имеет длину ≤p(n), причемx∈ LП ⇔ на x существует принимающее вычисление⇔ на x существует принимающее вычисление свременем ≤ p(n) и|w|≤ p(n)⇔ существует выполняющее значение переменныхдля задачи f L (x),заданной КНФ,Определимпри этом f L (x) вычисляется за полиномиальное время.множества дизъюнкций и их смысл.G1В любой момент времени i машинанаходится точно в одном состоянии.G2В любой момент времени i головкапросматривает точно одну ячейку.G3В любой момент времени i каждаяячейка содержит точно один символ A.G4В момент времени 0 вычисление находится в начальной конфигурациистадии проверки со входом x.G5Не более чем через p(n) шагов машина97G6G1переходит в состояние qY(принимает x).Для любого времени i, 0 ≤ i ≤ p(n) конфигурация машины в момент i +1 получается из конфигурации в момент i однократным применением команды машины.Описание дизъюнкций для функции f L .(Q( i,0) ∨ Q( i,1)∨...∨Q( i,r)),0 ≤ i ≤ p( n)(Q( i, j) ∨ Q( i, j ′))G20 ≤ i ≤ p( n)0 ≤ j < j′ ≤ r(H( i,− p( n)) ∨ H( i,− p( n) + 1)∨...∨H( i,p( n) + 1)),(H( i, j) ∨ H( i, j ′))G30 ≤ i ≤ p( n)0 ≤ i ≤ p( n)− p( n) ≤ j < j ′ ≤ p( n) + 1( a( i, j,0) ∨ a( i, j,1)∨...∨ a( i, j,v)),0 ≤ i ≤ p( n)( a( i, j,k) ∨ a( i, j,k ′))G40 ≤ i ≤ p( n)− p( n) ≤ j ≤ p( n) + 10 ≤ k < k′ ≤ v(Q(0,0)), (H(0,1)), ( a(0,0,0)), ( a(0,-1,0)),......( a(0,− p( n),0)), ( a(0,1,k1 )),...,( a(0,n,kn ))( a(0,n +1,0)),...,( a(0,p( n) +1,0))где x = ak1 ak2 ...

aknG5(Q( p( n),1))G6a) ( a( i, j,l),H( i, j),a( i, j,l))0 ≤ i < p( n)− p( n) ≤ j ≤ p( n) + 10≤ l ≤ vЗамечание. Дизъюнкция гарантирует, что если головка машины в момент iне просматривает ячейку j, то в момент i +1 ее содержимое не меняется.б) ∀ ( i, j,k,l)0 ≤ i < p( n)- p( n) ≤ j ≤ p( n) +10≤ l ≤ v(H( i, j) ∨ Q( i,k) ∨ a( i, j,l) ∨ H( i +1,i + ∆ ))(H( i, j) ∨ Q( i,k) ∨ a( i, j,l) ∨ Q( i +1,k ′))(H( i, j) ∨ Q( i,k) ∨ a( i, j,l) ∨ a( i +1, j,l ′))где ∆,k’,l’ определены командами машины:Если qk ∈ Q \ {qY ,qN }, то qk al → qk′ al ′ ∆ .98Если qk ∈ {qY ,qN },то ∆ = 0, k ′ = k, l ′ = k .Заметим, что число дизъюнкций в G6 - полином от n. Далее, если x∈ LП , тосуществует принимающее вычисление длины ≤ p(n) и выполнимы вседизъюнкции из G1,G2,G3,G4,G5,G6 и x∈ LП ⇔ существует выполняющийнабор для f L = G1 ⋅ G2 ⋅ G3 ⋅ G4 ⋅ G5 ⋅ G6 .

Теперь, для любого x∈ LПиндивидуальная задача f L (x) может быть построена за время, ограниченноеполиномом от n=|x|, при этом длина f L (x) также ограничена сверху полиномомот n.Таким образом, преобразование f L (x) может быть осуществлено за числодействий, полиномиально зависящее от n. При этом f L (x) имеет O(( p( n)) 2 )переменных и O(( p( n)) 2 ) - дизъюнкций. Так как П - произвольная задача из NP,то тем самым теорема доказана.99§ 16.