1632
правки
Изменения
м
rollbackEdits.php mass rollback
Рассмотрим язык <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>.
[[2-SAT]]
[[Категория:Классы сложности]]
