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