70
правок
Изменения
Нет описания правки
Рассмотрим произвольный язык <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 \, Rightarrow L_1 \le \overline L</tex>. Значит <tex>\overline L \in NPC</tex>.
В обратную сторону доказательство аналогично.
}}
{{Определение
|definition=
<tex>TAUT = \{\phi</tex> {{---}} булева формула <tex>| \forall x = (x_1, x_2, \ldots , x_m) \, \phi(x)=1\}</tex>.
}}
