editor
143
правки
Изменения
Нет описания правки
Вклассах, являющихся подмножествами <tex>\mathrm{P}</tex>, не используют Р-сведение по Карпу, так как оно оказывается бессмысленным. Для них применяется L-сведение с <tex>O(\log n)</tex> памятью. {{ Определение|definition=<tex>\mathrm{A} \in \mathrm{PC} \Leftrightarrow \mathrm{A} \in \mathrm{P}</tex> и <tex>\forall \mathrm{B} \in \mathrm{P} </tex> верно, что <tex>\mathrm{B} \leq_{\widetilde{L}} \mathrm{A}</tex>.}} {{ Определение|definition=<tex>\mathrm{A} \in \mathrm{NLC} \Leftrightarrow \mathrm{A} \in \mathrm{NL}</tex> и <tex>\forall \mathrm{B} \in \mathrm{NL} </tex> верно, что <tex>\mathrm{B} \leq_{\widetilde{L}} \mathrm{A}</tex>.}}
{{ Определение
