Бюрократы, editor, Администраторы
422
правки
Изменения
Нет описания правки
{{Лемма
|about=1
|statement=Язык <tex>L</tex> является <tex>\mathrm{coNP}</tex>-полным тогда и только тогда, когда <tex>\overline L</tex> является <tex>\mathrm{NP}</tex>-полным(то есть <tex>L \in \mathrm{coNP\mbox{-}C} \Leftrightarrow L \in \mathrm{co\mbox{-}NPC}</tex>).
|proof=Пусть <tex>L</tex> {{---}} <tex>\mathrm{coNP}</tex>-полный. Тогда <tex>L \in \mathrm{coNP}</tex> и <tex>\overline L \in \mathrm{NP}</tex>.
