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

Класс  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.  Тогда  для  любого  языка  L∈NP :  L< P R,  L’ < P R’.

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

NP ⊆ co-NP :  Пусть  L∈NP.  Тогда  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  допускается  детерминированной  машиной  Тьюринга  M1  (для  НМТ доказательство  аналогично),  имеющей  полиномиальное  ограничение  пространства  p(n).  По  теореме  11.3,  если  M1  допускает  вход  w,  то  делает  около c 1 +  p(⎢w ⎢)  шагов.

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

p (⎢w ⎢)  клеток  первой  ленты. 

  Преобразуя  M2  в  одноленточную  машину  M3,  можно  гарантировать,  что  M3 использует  не  более 1 +p (⎢w ⎢)  клеток  и  время  работы O(c2 p(⎢w ⎢)).

  Машина  M3  совершает  не  более  d⋅c 2 p(⎢w ⎢)  переходов  для  некоторой  константы  d,  поэтому  можно  выбрать  q(n) = 2 p(n) + log c d,  где  n – длина  входа.  Тогда  M3  совершает  не  более  cq(n)  шагов.  M2  всегда  останавливается, поэтому  то  же  делает  и  M3.  M1  допускает  L,  поэтому  M2  и  M3  допускают  L.  Таким  образом,  M3  удовлетворяет  теореме.