Изменения

Перейти к: навигация, поиск

Классы L, NL, coNL. NL-полнота задачи о достижимости

6 байт убрано, 18:32, 3 июня 2012
→‎NL-полнота
Алгоритм:
1. #Начиная с вершины <tex> s </tex> недетерминированно переходим в одну из вершин, смежных с ней. (Очевидно, для этого необходимо конечное число переменных)
2. #Проверяем, правда ли, что текущая вершина совпадает с <tex> t </tex>. Если это так, возвращает TRUE.
3. #Отдельно считаем количество пройденных вершин. Как только это число превышает количество вершин в графе, возвращаем FALSE, так как посетили некоторую вершину дважды.
Таким образом в каждый момент алгоритму достаточно хранить текущую вершину, количество посещенных вершин, финальную вершину <tex> t </tex> и некоторое число вспомогательных переменных, для совершения переходов. Все эти переменные принимают значения не более, чем максимальный номер вершины, то есть как раз занимают <tex> O(\log n) </tex> памяти.
Berezhkovskaya
editor
143
правки
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/23517»

Навигация