patternMinor
Is 3-UNSAT problem coNP-complete?
Viewed 0 times
unsatproblemcompleteconp
Problem
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?
Solution
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$.
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$.
Context
StackExchange Computer Science Q#143238, answer score: 2
Revisions (0)
No revisions yet.