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