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