Изменения

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

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

Используя логарифмическое количество памяти Так как <tex>A</tex> '''NL'''-полон, то существует такая функция <tex>f</tex> (использующая ''BO'' сводится к языку (log ''An'') дополнительной памяти), который уже лежит в что <tex>x \in B \Leftrightarrow f(x) \in A</tex>. <tex>A</tex> принадлежит '''L''', поэтому мы можем определить принадлежность <tex>x</tex> языку <tex>B</tex> с необходимыми условиями.

Тонкость состоит в томОднако, что мы не можем результат работы функции <tex>f</tex> сохранить невозможно, так как он может занимать более ''O''(log ''n'') памяти. Но ограничение по времени отсутствует, поэтому для определения некоторого элемента результата работы функции (который запрашивает детерминированная машина Тьюринга, соответствующая языку <tex>A</tex>, для определения истинности <tex>f(x) \in A</tex>) будем просто перезапускать функцию и запоминать лишь необходимый элемент ее результата.