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

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(p2(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 < i, j, k > + ¬ H< i, t >  +  ¬ S< k, t >  +  ∑ ( C<i, jl, t+1 >

S< kl, t+1> H< il, t+1>),  i

где  l  пробегает  по  всем  шагам  машины  M,  когда  M  обозревает  символ  Xj  в  состоянии  qk.  Т. е.  для  каждой  тройки  < q, X, d >  из  δ (q k, Xj)  существует  одно  значение  l,  для  которого  Xjl = X,  q kl  =  q  и  число  il  равно  i -1,  i  или  i+1  в  зависимости  от  значения  d,  равного  соответственно  L,  S, R.  Поскольку  машина  M  недетерминированная,  таких  троек 

< q, X, d >  может  быть  несколько,  но  их  конечное  число,  таким  образом 

Ei j k t  имеет  ограниченную  длину, не  зависящую от n. Формула  E  имеет  длину  O(p2(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  находится  в  начальном  состоянии  q1; 

H< 1, 0  >  утверждает,  что  M  в  момент  t=0  обозревает  самую  левую  ячейку  ленты; 

  П  C< i, j i, 0 >  утверждает, что первые  n клеток вначале содержат входную цепочку  ω;

1≤ i ≤ n

  П  C< i, 1, 0 > утверждает,  что  остальные  клетки  вначале  пусты.

n≤ i ≤p( n)

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

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

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

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

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

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

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

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

Доказательство. Покажем,  что  выполнимость  формул  в  КНФ  полиномиально  сводится  к  3-выполнимости. Заменим  каждый  член  (x1 + x2+…+x k),

на  (x 1 + x 2 + y 1)(x 3 + y 1 + y 2)( x 4 + y 2 + y 3)…(x k -1 + x k+ yk -3)

(k ≥ 4),  где  y 1, y 2,…,y k-3  -  новые  переменные.

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

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

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

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

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

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

Быстрая сортировка  как  пример  рандомизированного  алгоритма. Язык  рандомизированной  машины  Тьюринга. Класс  RP. Класс  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  (безошибочные,  вероятностные  полиномиальные)  также  используют  случайные  числа,  но  алгоритм  дает  ответ:  “да”,  если  вход  принадлежит  языку,  и  “нет” – в  противном  случае. Ожидаемое  время  работы  алгоритма  полиномиально,  однако  возможно,  что  выполнение  алгоритма  потребует  больше  времени,  чем  полиномиальное.