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