2
$\begingroup$

I have shown that a language $A$ is NP-complete $\iff$ its complement $\overline{A}$ is co-NP-complete.

Also, I have shown that CNF-SAT is NP-complete.

Since UNSAT is the complement of SAT, then CNF-UNSAT is the complement of CNF-SAT and CNF-UNSAT is co-NP-complete, right?

$\endgroup$
1
  • 1
    $\begingroup$ Right. ${{{}}}$ $\endgroup$
    – Wojowu
    Commented May 10, 2020 at 11:27

0

Reset to default

You must log in to answer this question.