NL-полнота задачи о достижимости в графе — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Доказательство NL-трудности задачи STCON)
Строка 2: Строка 2:
 
Даны ориентированный граф <tex> G = \langle V, E \rangle </tex> и две вершины <tex> s, t</tex> в нем. Необходимо проверить, правда ли, что в графе <tex> G </tex> существует путь из вершины <tex> s </tex> в вершину <tex> t </tex>. Эту задачу принято называть <tex> st-connectivity </tex> или <tex> STCON </tex>.
 
Даны ориентированный граф <tex> G = \langle V, E \rangle </tex> и две вершины <tex> s, t</tex> в нем. Необходимо проверить, правда ли, что в графе <tex> G </tex> существует путь из вершины <tex> s </tex> в вершину <tex> t </tex>. Эту задачу принято называть <tex> st-connectivity </tex> или <tex> STCON </tex>.
  
== Утверждение ==
+
== Теорема ==
 
Задача <tex> STCON </tex> [[NL-полнота|NL-полна]].
 
Задача <tex> STCON </tex> [[NL-полнота|NL-полна]].
  
Строка 10: Строка 10:
 
=== Доказательство принадлежности задачи STCON классу NL ===
 
=== Доказательство принадлежности задачи STCON классу NL ===
  
Для доказательства необходимо предъявить алгоритм для недетерминированной машины Тьюринга, который использует конечное число переменных, каждая из которых занимает <tex> O(log n) </tex> памяти, где <tex> n </tex> - размер входа для задачи и за время порядка <tex> O(poly(n)) </tex> решает эту задачу.
+
Для доказательства необходимо предъявить алгоритм для недетерминированной машины Тьюринга, который использует конечное число переменных, каждая из которых занимает <tex> O(\log n) </tex> памяти, где <tex> n </tex> - размер входа для задачи и за время порядка <tex> O(poly(n)) </tex> решает эту задачу.
  
 
Алгоритм:
 
Алгоритм:
Строка 20: Строка 20:
 
3. Отдельно считает количество пройденных вершин. Как только это число превышает количество вершин в графе, то алгоритм возвращает FALSE, так как посетил некоторую вершину дважды.
 
3. Отдельно считает количество пройденных вершин. Как только это число превышает количество вершин в графе, то алгоритм возвращает FALSE, так как посетил некоторую вершину дважды.
  
Таким образом в каждый момент алгоритму достаточно хранить текущую вершину, количество посещенных вершин, финальную вершину <tex> t </tex> и некоторое число вспомогательных переменных, для совершения переходов. Все эти переменные принимают значения не более, чем максимальный номер вершины, то есть как раз занимают <tex> O(log n) </tex> памяти.
+
Таким образом в каждый момент алгоритму достаточно хранить текущую вершину, количество посещенных вершин, финальную вершину <tex> t </tex> и некоторое число вспомогательных переменных, для совершения переходов. Все эти переменные принимают значения не более, чем максимальный номер вершины, то есть как раз занимают <tex> O(\log n) </tex> памяти.
 
 
Так как, если из <tex> s </tex> существует путь в <tex> t </tex>, то он имеет длину не более, чем количество вершин в графе, то алгоритм корректно возвращает FALSE.
 
  
 
=== Доказательство NL-трудности задачи STCON ===
 
=== Доказательство NL-трудности задачи STCON ===
 
Необходимо показать, что любая задача из класса [[NL]] сводится к задаче STCON с использованием не более, чем логарифмической памяти.
 
Необходимо показать, что любая задача из класса [[NL]] сводится к задаче STCON с использованием не более, чем логарифмической памяти.
  
Необходимо по данной задаче из [[NL]] построить тройку <tex> <G, s, t> </tex>, решение задачи STCON для которой будет эквивалентно решению данной задачи.
+
Необходимо по данной задаче из [[NL]] построить тройку <tex> \langle G, s, t \rangle </tex>, решение задачи STCON для которой будет эквивалентно решению данной задачи.
  
Любая нмашина Тьюринга, которая принимает некоторый язык L из [[NL]] использует не более, чем логарифмическое количество ячеек на ленте и таким образом возможных состояний этой машины Тьюринга <tex> O(poly(n)) </tex>. Состоянием машины Тьюринга считается ее внутреннее состояние, позиция головки на ленте и содержимое рабочей ленты. Каждому возможному состоянию машины Тьюринга будет соответствовать некоторая вершина в <tex> G </tex>, а каждому переходу из этого состояния в другое (которых в недетерминированной машине Тьюринга не более, чем некоторое конечное число), ребро в графе <tex> G </tex>. За вершину <tex> s </tex> принимается вершина, соответствующая начальному состоянию машины, а из каждой вершины, соответствующей некоторому допускающему состоянию, добавляется переход в выделенную вершину <tex> t </tex>.
+
Любая машина Тьюринга, которая принимает некоторый язык L из [[NL]] использует не более, чем логарифмическое количество ячеек на рабочей ленте и таким образом возможных мгновенных описаний этой машины Тьюринга <tex> O(poly(n)) </tex>. Мгновенным описанием машины Тьюринга считается ее внутреннее состояние, позиция головки на ленте и содержимое рабочей ленты. Каждому возможному мгновенному описанию машины Тьюринга будет соответствовать некоторая вершина в <tex> G </tex>, а каждому переходу из этого описания в другое (которых в недетерминированной машине Тьюринга не более, чем некоторое конечное число), ребро в графе <tex> G </tex>. За вершину <tex> s </tex> принимается вершина, соответствующая начальному состоянию машины, а из каждой вершины, соответствующей некоторому допускающему состоянию, добавляется переход в выделенную вершину <tex> t </tex>.
  
 
Очевидно, что для любого слова, из языка L, то есть принимаемого данной машиной Тьюринга, будет существовать путь из <tex> s </tex> в <tex> t </tex> в построенном графе <tex> G </tex>. А, если для некоторого слова не из L в <tex> G </tex> существует путь из <tex> s </tex> в <tex> t </tex>, то он соответствует некоторой корректной последовательности переходов в изначальной машине, таким образом слово должно было приниматься этой недетерминированной машиной.
 
Очевидно, что для любого слова, из языка L, то есть принимаемого данной машиной Тьюринга, будет существовать путь из <tex> s </tex> в <tex> t </tex> в построенном графе <tex> G </tex>. А, если для некоторого слова не из L в <tex> G </tex> существует путь из <tex> s </tex> в <tex> t </tex>, то он соответствует некоторой корректной последовательности переходов в изначальной машине, таким образом слово должно было приниматься этой недетерминированной машиной.

Версия 15:35, 15 апреля 2010

Формулировка задачи

Даны ориентированный граф [math] G = \langle V, E \rangle [/math] и две вершины [math] s, t[/math] в нем. Необходимо проверить, правда ли, что в графе [math] G [/math] существует путь из вершины [math] s [/math] в вершину [math] t [/math]. Эту задачу принято называть [math] st-connectivity [/math] или [math] STCON [/math].

Теорема

Задача [math] STCON [/math] NL-полна.

Доказательство

Для доказательства NL-полноты необходимо показать, что эта задача NL-трудная и принадлежит классу NL.

Доказательство принадлежности задачи STCON классу NL

Для доказательства необходимо предъявить алгоритм для недетерминированной машины Тьюринга, который использует конечное число переменных, каждая из которых занимает [math] O(\log n) [/math] памяти, где [math] n [/math] - размер входа для задачи и за время порядка [math] O(poly(n)) [/math] решает эту задачу.

Алгоритм:

1. Начиная с вершины [math] s [/math] недетерминированно переходит в одну из вершин, смежных с ней. (Очевидно, для этого необходимо конечное число переменных)

2. Проверяет, правда ли, что текущая вершина совпадает с [math] t [/math]. Если это так, возвращает TRUE.

3. Отдельно считает количество пройденных вершин. Как только это число превышает количество вершин в графе, то алгоритм возвращает FALSE, так как посетил некоторую вершину дважды.

Таким образом в каждый момент алгоритму достаточно хранить текущую вершину, количество посещенных вершин, финальную вершину [math] t [/math] и некоторое число вспомогательных переменных, для совершения переходов. Все эти переменные принимают значения не более, чем максимальный номер вершины, то есть как раз занимают [math] O(\log n) [/math] памяти.

Доказательство NL-трудности задачи STCON

Необходимо показать, что любая задача из класса NL сводится к задаче STCON с использованием не более, чем логарифмической памяти.

Необходимо по данной задаче из NL построить тройку [math] \langle G, s, t \rangle [/math], решение задачи STCON для которой будет эквивалентно решению данной задачи.

Любая машина Тьюринга, которая принимает некоторый язык L из NL использует не более, чем логарифмическое количество ячеек на рабочей ленте и таким образом возможных мгновенных описаний этой машины Тьюринга [math] O(poly(n)) [/math]. Мгновенным описанием машины Тьюринга считается ее внутреннее состояние, позиция головки на ленте и содержимое рабочей ленты. Каждому возможному мгновенному описанию машины Тьюринга будет соответствовать некоторая вершина в [math] G [/math], а каждому переходу из этого описания в другое (которых в недетерминированной машине Тьюринга не более, чем некоторое конечное число), ребро в графе [math] G [/math]. За вершину [math] s [/math] принимается вершина, соответствующая начальному состоянию машины, а из каждой вершины, соответствующей некоторому допускающему состоянию, добавляется переход в выделенную вершину [math] t [/math].

Очевидно, что для любого слова, из языка L, то есть принимаемого данной машиной Тьюринга, будет существовать путь из [math] s [/math] в [math] t [/math] в построенном графе [math] G [/math]. А, если для некоторого слова не из L в [math] G [/math] существует путь из [math] s [/math] в [math] t [/math], то он соответствует некоторой корректной последовательности переходов в изначальной машине, таким образом слово должно было приниматься этой недетерминированной машиной.