NL-полнота — различия между версиями
Ulyantsev (обсуждение | вклад) (Новая страница: «В классе '''NL''' выделяют подкласс полных в этом классе задач. ===Определение=== Язык ''L'' яв…») |
Ulyantsev (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
===Определение=== | ===Определение=== | ||
| − | Язык '' | + | Язык ''A'' является '''NL'''-полным ('''NLC'''), если он принадлежит классу '''NL''' и любой другой язык ''A<nowiki>'</nowiki>'' из '''NL''' можно [[сведение по Карпу|свести по Карпу]] к ''A'', притом сведение будет использовать логарифмическое количество памяти. То есть сведение не может сохранить входные данные, но может неограниченно писать на выходную ленту и читать со входной. |
==Примеры== | ==Примеры== | ||
| + | |||
| + | [[NL-полнота задачи о достижимости в графе]] | ||
Версия 17:17, 8 апреля 2010
В классе NL выделяют подкласс полных в этом классе задач.
Определение
Язык A является NL-полным (NLC), если он принадлежит классу NL и любой другой язык A' из NL можно свести по Карпу к A, притом сведение будет использовать логарифмическое количество памяти. То есть сведение не может сохранить входные данные, но может неограниченно писать на выходную ленту и читать со входной.
