165
правок
Изменения
Нет описания правки
===Определение===
Язык <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>, притом сведение будет использовать логарифмическое количество памяти.
