70
правок
Изменения
Нет описания правки
{{Лемма
|about=1
|statement=<tex>L \in coNPC \Leftrightarrow \overline L \in NPC</tex>
|proof=Пусть <tex>L \in coNPC</tex>. Тогда <tex>L \in coNP</tex> и <tex>\overline L \in NP</tex>.
В обратную сторону доказательство аналогично.
}}
{{Определение
|definition=
<tex>TAUT = \{\phi | \forall x \, \phi(x)=1\}</tex>.
}}
{{Лемма
|about=2
|statement=<tex>TAUT \in coNPC</tex>
|proof=<tex>\overline {TAUT} = \{\phi | \exists x : \phi(x) \ne 1\} = \{\phi | \overline {\phi} \in SAT\}</tex>, то есть <tex>\overline {TAUT} \in NPC</tex>. Тогда по лемме 1 <tex>TAUT \in coNPC</tex>.
}}
{{Определение
|definition=
