Изменения
→Доказательство
Рассмотрим язык <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>.
