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