NL-полнота
Версия от 17:17, 8 апреля 2010; Ulyantsev (обсуждение | вклад)
В классе NL выделяют подкласс полных в этом классе задач.
Определение
Язык A является NL-полным (NLC), если он принадлежит классу NL и любой другой язык A' из NL можно свести по Карпу к A, притом сведение будет использовать логарифмическое количество памяти. То есть сведение не может сохранить входные данные, но может неограниченно писать на выходную ленту и читать со входной.
