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