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

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.