70
правок
Изменения
Нет описания правки
|proof=Пусть <tex>L \in coNPC</tex>. Тогда <tex>L \in coNP</tex> и <tex>\overline L \in NP</tex>.
Рассмотрим произвольный язык <tex>L_1 \in NP</tex>. Тогда <tex>\overline {L_1} \in coNP</tex>. Так как <tex>L \in coNPC</tex>, то <tex>\overline {L_1} \le L</tex>, [[Сведение по Карпу. Трудные и полные задачи|следовательно]] <tex>L_1 \le \overline L</tex>(по [[Сведение по Карпу. Трудные и полные задачи|лемме]]).
Получили, что <tex>\overline L \in NP</tex> и <tex>\forall L_1 \in NP \, L_1 \le \overline L</tex>. Значит <tex>\overline L \in NPC</tex>.
