Изменения

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

Язык ''A'' является '''NL'''-полным ('''NLC'''), если он принадлежит классу '''NL''' и любой другой язык <tex>A'</tex> из '''NL''' можно [[сведение по Карпу|свести по Карпу]] к <tex>A</tex>, притом сведение будет использовать логарифмическое количество памяти. То есть сведение не может сохранить входные данные, но может неограниченно писать на выходную ленту и читать со входной. ==Теорема== Если в классе '''[[L]]''' существует такой язык <tex>A</tex>, что он '''NL'''-полон, то '''NL''' = '''L'''. ===Доказательство=== Рассмотрим язык ''B'' <tex>B</tex> из класса '''NL'''. Для каждого слова ''x'' <tex>x</tex> необходимо определять его принадлежность ''B'' используя лишь детерминированные выборы и ''O''(log ''n'') дополнительной памяти. Так как ''A'' '''NL'''-полон, то существует такая функция ''f'' <tex>f</tex> (использующая ''O''(log ''n'') дополнительной памяти), что <tex>x \in B \Leftrightarrow f(x) \in A</tex>. Используя логарифмическое количество памяти ''B'' сводится к языку ''A'', который уже лежит в '''L'''. Тонкость состоит в том, что мы не можем сохранить  ==ПримерыNL-полных задач==