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

Если  (M,ω) ∉ Lu,  т. е.  M  не  допускает  вход  ω,  тогда  M ’  прекращает  работу, не  допуская  свой  вход  x.  L(M’ ) =  ∅,  следовательно,

L(M ’ ) ∉℘,  а  M’ ∉ L℘.  Если  (M,ω) ∈ Lu,  то  L(M’ ) = L  и  M’ ∈ L℘.

  Схема  такого  алгоритма  приведена  на  рис. 

  Машина  M’  имеет  две  ленты:  на  первой  записан  код  машины  M  и  входа  ω,  на  второй  –  код  машины  ML,  допускающей  язык  L.

  Работа  моделируемой  машины  M’  состоит  в  следующих  шагах:

Имитируется  работа  универсальной  машины  U  на  входе  (M,ω). Если  (M,ω) ∉ L u,  т. е.  M  не  допускает  вход  ω,  то M’  прекращает  работу, не  допуская  свой  вход  x. Если  (M,ω) ∈ L u,  т. е.  M  допускает  ω,  то  далее  M’  имитирует  работу  машины  ML  на  входе  x  и  допускает,  так  как  x∈L  и  ML  допускает  язык  L.

Таким  образом,  для  рассматриваемого  свойства  ℘, где ∅∉℘, 

Lu  <  L℘ ,  следовательно,  язык  L℘  неразрешим.

b)  Допустим,  что  ∅∈℘.  Рассмотрим  ℘,  дополнение  свойства ℘, т. е.  множество  РП-языков,  не  обладающих  свойством ℘.  Свойство  ℘  содержит  ∅,  так  что  как  в  части  a)  можно  доказать  неразрешимость  языка  L℘  .  Поскольку  язык  L℘  есть  множество  кодом  машин,  не  допускающих  свойство ℘,  то  L℘  = L℘ .  Если  предположить,  что  язык  L℘  разрешимый,  то  по  теореме  Поста, его  дополнение  -  рекурсивный  язык,  что  не  верно.

Неразрешимые  проблемы,  связанные  с  языками  машин  Тьюринга:

Пуст  ли  язык,  допускаемый  машиной  Тьюринга? Конечен  ли  язык,  допускаемый  машиной  Тьюринга? Регулярен  ли  язык,  допускаемый  машиной  Тьюринга? Контекстно-свободен  язык,  допускаемый  машиной  Тьюринга?

Разрешимые (тривиальные)  проблемы,  связанные  с  языками  машины  Тьюринга:

Содержит  ли  машина  Тьюринга  данное  число  состояний? Существует  ли  вход,  допускаемый  машиной  Тьюринга  за  данное  число  переходов?

Тема 3.  Труднорешаемые  проблемы.

§ 1.  Классы  P  и  NP.

§ 2.  Проблемы,  решаемые  за  полиномиальное  время.

Алгоритм  Крускала. Сортировки.

§ 3.  Полиномиальное  сведение.

§ 4.  NP – полные  проблемы.

  4.1.  Проблема  выполнимости  булевой  функции (ВЫП).

  4.2.  NP – полнота  проблемы  выполнимости  КНФ  (КНФ).

  4.3.  NP – полнота  проблемы  выполнимости  3-КНФ  (3-КНФ).

Проблемы, к  которым  сводится  проблема  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) ∀ v1, v2 ∈ V  ∃!  v1  a v2  (путь  в  S).

Если  к  дереву  S  добавить  ребро  (v1,v2)∈ E \ T,  то  возникнет  точно  один  цикл.

Доказательство.  a)  В  противном  случае  S  содержит  цикл,  что  невозможно.  b)  В  противном  случае  в  S  уже  был  цикл,  что  невозможно.

Лемма 2. Пусть  G = (V, E) -  связный  неориентированный  граф,  ребрам  которого  приписаны  целочисленный  вес  f :  E →  N.

Если  {(V1, T1), … , (Vk, Tk)}- лес, где  V =  ∪  Vi  ,  T =  ∪  Ti  (k > 1); 

  i=1..k  i=1..k 

e = (v, w) ∈ E \ T – ребро  наименьшего  веса  в  E \ T,  где  v ∈ V1,  w ∉ V1. 

Тогда  найдется  остовное  дерево,  содержащее  T∪{e},  веса,  меньшего  веса  любого  остовного  дерева,  содержащего  T.

Доказательство. Допустим,  что  S’ = (V, T’ ) – остовное  дерево  графа  G,  содержащее  T  и  не  содержащее  e,  наименьшего  веса  среди  остовных  деревьев,  содержащих  T∪{e}.  По  лемме 1  добавление  к  S’  ребра e  образует  цикл.  Этот  цикл  будет  содержать  ребро  e’  = (v’, w’ ) ≠ e,  где

v’ ∈ V1, w’ ∉ V1.  По  условие  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)).