Просмотр исходного текста страницы NL-полнота

В классе '''[[NL]]''' выделяют подкласс полных в этом классе задач. 

===Определение===

Язык ''A'' является '''NL'''-полным ('''NLC'''), если он принадлежит классу '''NL''' и любой другой язык ''A<nowiki>'</nowiki>'' из '''NL''' можно [[сведение по Карпу|свести по Карпу]] к ''A'', притом сведение будет использовать логарифмическое количество памяти. То есть сведение не может сохранить входные данные, но может неограниченно писать на выходную ленту и читать со входной.

==Примеры==

[[NL-полнота задачи о достижимости в графе]]