HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Is 3-UNSAT problem coNP-complete?

Submitted by: @import:stackexchange-cs··
0
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$.

Context

StackExchange Computer Science Q#143238, answer score: 2

Revisions (0)

No revisions yet.