Изменения

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

Рассмотрим язык ''B'' <tex>B</tex> из класса '''NL'''. Для каждого слова ''x'' <tex>x</tex> необходимо определять его принадлежность ''B'' используя лишь детерминированные выборы и ''O''(log ''n'') дополнительной памяти. Так как ''A'' '''NL'''-полон, то существует такая функция ''f'' <texdpi="100">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'') памяти. Но ограничение по времени отсутствует, поэтому для определения некоторого элемента результата работы функции будем просто перезапускать функцию и запоминать лишь необходимый элемент ее результата.