coNP完全
coNP-complete
定義
$ L \text{ is $\mathbf{coNP}$-complete} \iff L \text{ is $\mathbf{coNP}$-hard} \land L \in \mathbf{coNP}
性質
TAUTOLOGYはcoNP完全
$ \text{TAUTOLOGY} := \{\phi \in \text{Boolean formula}\ |\ \text{$\phi$ is tautology}\}
Proof.
$ \phi \in \overline{\text{SAT}} \iff \lnot\phi \in \text{TAUTOLOGY}より$ \overline{\text{SAT}} \le_p \text{TAUTOLOGY}$ \text{TAUTOLOHUGY}はcoNP完全 ❏ 関連