0
$\begingroup$

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!

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ 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? $\endgroup$
    – Raphael
    Commented Nov 24, 2014 at 19:17
  • $\begingroup$ @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? $\endgroup$
    – zarathustra
    Commented Nov 25, 2014 at 9:07
  • 1
    $\begingroup$ @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. $\endgroup$
    – Raphael
    Commented Nov 25, 2014 at 10:01

1 Answer 1

Reset to default
1
$\begingroup$

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!

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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