Методические указания к курсу ”Сложность вычислений” (стр. 10 )

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

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

  Алфавит  булевых  формул  содержит  пропозициональные  переменные,  символы  операций:  &,  ∨,  ¬ ,  символы  1, 0,  вспомогательные  символы: 

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

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

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

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

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

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

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

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

  Покажем,  что  произвольный  язык  L  из  NP  полиномиально  сводится  к  языку  ВЫП.  Для  языка  L ∈ NP  найдется  недетерминированная  одно - ленточная  машина  Тьюринга, обрабатывающая  вход  ω  длины  n  не  более,  чем  за  p(n)  шагов  вдоль  любой  ветви.  По  M, ω  будем  строить  булеву  формулу  ω0,  выполнимую  тогда  и  только тогда,  когда  M  допускает  ω.  Сводящий  алгоритм  должен  иметь  полиномиальную  сложность.  Пусть  M  имеет  состояния  q1, q2 ,…,q s  и  ленточные  символы  X1, X 2,…,X m. Если  M  допускает  вход  ω  длины  n,  то  делает  это  не  более,  чем  за  p(n)  шагов.  В  этом  случае  найдется  последовательность  МО  Q0, Q1,…,Q q,  где  Q0 – начальное, а  Qq  -  заключительное  (допускающее)  МО,  Qi -1 ├  Q i  для  1≤ i ≤q,  q ≤ p(n),  и  ни  одно МО  не  занимает  на  ленте  более  p(n)  клеток.

  Булева  функция  ω0,  которую  мы  собираемся  построить,  должна  моделировать  последовательность  МО, проходимых  машиной,  и  принимает  значение  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)2),  их  представление  двоичными  числами  займет не  более  c log n  разрядов,  где  c – константа,  зависящая  от  p.  Из  этих  пропозициональных  переменных  построим  функцию  ω0,  следуя  структуре  последовательности  МО  Q0, Q1,…,Q q.

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

U (x 1,…,x r)  = (x 1 +…+ x r ) ( П (¬x i  + ¬x j )), 

  i ≠ j

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

  Если машина  M  допускает  вход  ω,  то  найдется  последовательность  МО  Q0, Q1,…,Qq,  проходимых  машиной  в  ходе  обработки  цепочки  ω.

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

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

в  каждом  МО  головка  обозревает  одну  клетку; в  каждом  МО  в  каждой  клетке  записан  один  символ; каждое  МО  содержит  одно  состояние; при  переходе  Q i-1 ├  Q i  (1≤ i ≤ p(n))  изменяется  разве  что  содержимое  обозреваемой  ячейки; переход Q i-1 ├  Q i  (1≤ i ≤ p(n))  осуществляется  в  соответствии  с  функцией  переходов  машины  M; Q0  - начальное  МО; Q p( n)  -  заключительное  МО.

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

1. A  =  A 0 A1…A p (n)  утверждает,  что  в  каждый  момент  времени  маши

на  M  обозревает  в  точности  одну  клетку,  соответственно  At  утверждает,  что  в  момент  времени  t  обозревается  точно  одна  клетка,  где

At = U (H< 1, t >, …,H< p(n), t >).  Формула  A  имеет  длину  O(p3(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(p2(n)).