The 3-SAT problem, i.e. the problem whether a given Boolean formula consisting of clauses of at most 3 literals is known to be NP-complete. Then it’s complement, i.e. whether such a formula is unsatisfiable, is coNP-complete, right?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Let $\ell\subseteq\Sigma^*$ be some language. The complement of $\ell$ is$$\ell^c=\Sigma^*\setminus \ell.$$ The class CoNP is complexity class (set of languages) whose complement is in NP. Formally
$$CoNP=\{\ell\mid \ell^c\in NP\}.$$ According to this link, because of $3-SAT\in NPC$, so $3-USAT\in CoNPC$.
