From our computational complexity, there's a question asking to prove 3CLIQUE is decidable.

The definition of 3CLIQUE is:
$$\{(V,E) : G = (V,E)\text{ is an undirected graph that contains a clique of size 3}\}.$$

I know this is an NP problem, and NP is a set of problems that easy to verify but hard to solve, but I don't know how to prove. Is there anyone who can help me on this?

  • 1
    $\begingroup$ Is the question to show decidability, or to show that it's efficiently decidable? $\endgroup$ – templatetypedef Dec 3 '16 at 1:59
  • $\begingroup$ "NP is a set of problems that easy to verify but hard to solve" -- wrong. NP includes many problems that are easy to solve. $\endgroup$ – Raphael Dec 3 '16 at 11:27
  • $\begingroup$ What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – Raphael Dec 3 '16 at 11:27
  • $\begingroup$ Your question is a very basic one. Let me direct you towards our reference questions which cover some fundamentals you seem to be missing in detail. Please work through the related questions listed there, try to solve your problem again and edit to include your attempts along with the specific problems you encountered. Good luck! $\endgroup$ – Raphael Dec 3 '16 at 11:28

In fact, NP is not the set of problems that are easy to verify but hard to solve. It is just the set of problems that are easy to verify. NPC, the set of NP-complete problems, is the set of problems that are easy to verify but seem hard to solve.

Your problem is in NP but it isn't NP-complete (unless P=NP), since it's also in P. That is, it can be solved in polynomial time. To prove this, you need to give a polynomial time algorithm that, given a graph $G=(V,E)$, determines whether it contains a clique of size 3. I trust that you are able to do it yourself.


You just need to come up with an algorithm – any algorithm, no matter how dumb or inefficient – to solve the problem. By proving that there's an algorithm, you've proved that it's decidable, since that's what decidable means.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy