3
$\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$
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, privacy policy and cookie policy

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