4
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.