Изменения

Язык <tex dpi="100">A</tex> является <tex dpi="100">NL</tex>-полным ('''NLC'''), если он принадлежит классу <tex dpi="100">NL</tex> и любой другой язык <tex dpi="100">A'</tex> из <tex dpi="100">NL</tex> можно [[сведение по Карпу|свести по Карпу]] к <tex dpi="100">A</tex>, притом сведение будет использовать логарифмическое количество памяти. Язык <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> необходимо определять его принадлежность ''<tex>B'' </tex> используя лишь детерминированные выборы и ''O''(log ''n'') дополнительной памяти.

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

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