# Some questions about NP / coNP / CSP

I need help with the following mock exam questions. True or false?

1.) If a non-trivial $(\neq \emptyset, \Sigma^*)$ finite set is NP-complete, then $P = NP$.

True. Every finite set is in $P$ and because of the $NP$-completeness every set in $NP$ can be reduced to this set. Is it right?

2.) $NP \subseteq coNP$ $\Leftrightarrow$ $NP = coNP$.

I don't know if the "$\Rightarrow$" case holds. I only know $P \subseteq coNP$ and $P \subseteq NP$.

3.) For every fixed $k$ the problem $k$-$CLIQUE$ can be modeled as a Constraint Satisfaction Problem.

I have no idea. We've had $3$-$COLOR$ and $3$-$SAT$ as examples but also the fact that not every NP-problem can be expressed in terms of a CSP.

Thanks in advance!

• Please restrict yourself to one question per post. Furthermore, dumping exercise problems here without any attempt we can use to find out what your real problems are is not a good idea, neither is having your solutions checked. So, what have you tried (for 2) and 3)) and where did you get stuck? – Raphael Nov 24 '14 at 19:17
• @Raphael: I thought the question was OK, but now what is the best course of action for me? Should I delete my answer and wait until the OP edits his question to undelete it? – zarathustra Nov 25 '14 at 9:07
• @rosebud Nah, the damage (if any) is done. (Mostly I'm concerned about answerers encouraging "bad" posting behaviour; we don't want Computer Science to become a homework assistance portal.) Thanks for asking, though! You may be interested in this list of common complaints about questions. – Raphael Nov 25 '14 at 10:01

## 1 Answer

2) Suppose that $\mathsf{NP} \subseteq \mathsf{coNP}$: in particular, SAT is in $\mathsf{coNP}$, and its complement coSAT, the set of boolean formulas that are not satisfiable, is in $\mathsf{NP}$. But coSAT is coNP-complete, so that we have a coNP-complete language in $\mathsf{NP}$, i.e. $\mathsf{coNP} \subseteq \mathsf{NP}$.

3) This depends on your definition of a CSP, I guess. Following the definition of a non-uniform CSP, the constraint satisfaction problem of a relational structure $\Gamma$ is the set of relational structures $\Delta$ on the same signature such that $\Delta$ homomorphically maps to $\Gamma$. Here, the signature is $\{E\}$, where $E$ is a binary relational symbol that indicates adjacency in graphs. Suppose that there exists $\Gamma$ such that $\mathrm{CSP}(\Gamma)$ is the $k$-CLIQUE problem. Then, letting $K_k$ be the $k$-clique, we have that $K_k$ homomorphically maps to $\Gamma$. But if $v$ is any vertex of $K_k$, we have that $\{v\}$ homomorphically maps to $K_k$, and since the composition of homomorphisms is a homomorphism, we have that $\{v\}$ has a homomorphism to $\Gamma$, a contradiction since $\{v\}$ does not contain a $k$-clique. Thus, the k-CLIQUE problem cannot be represented as a non-uniform constraint satisfaction problem.

Please let me know if the definition I used for the CSP is not the one you are used to!