202
правки
Изменения
Нет описания правки
Рассмотрим язык <tex>B</tex> из класса '''NL'''.
Для каждого слова <tex>x</tex> необходимо определять его принадлежность <tex dpi="100">B</tex> используя лишь детерминированные выборы и ''O''(log ''n'') дополнительной памяти.
Так как <tex>A</tex> '''NL'''-полон, то существует такая функция <tex>f</tex> (использующая ''O''(log ''n'') дополнительной памяти), что <tex>x \in B \Leftrightarrow f(x) \in A</tex>.
Однако, результат работы функции <tex>f</tex> сохранить невозможно, так как он может занимать более ''O''(log ''n'') памяти.
Но ограничение по времени отсутствует, поэтому для определения некоторого элемента результата работы функции (который запрашивает детерминированная машина Тьюринга, соответствующая языку <tex>A</tex>, для определения истинности <tex>f(x) \in A</tex>) будем просто перезапускать функцию и запоминать лишь необходимый элемент ее результата.
==Примеры NL-полных задач==
[[NL-полнота задачи о достижимости в графе]]
[[2-SAT]]
[[Категория:Классы сложности]]
