Can we prove that the 3 coloring graph problem (where no two adjacent nodes have same color) is NP instead of NP-complete?

$$\mathrm{3COLOR} = \{\langle G \rangle \mid G \text{ is colorable with 3 colors}\}$$

  • $\begingroup$ It sounds like you want to prove 3COLOR belongs to NP after you have proved it is NP-complete. Is that your intention? $\endgroup$ – John L. May 5 '19 at 19:13
  • 1
    $\begingroup$ This seems like a homework question. What have you tried so far? Have your proved 3-Coloring is NP-complete already? To prove it is NP you need a polytime verifier for a certificate of 3-Coloring. Can you think of one? $\endgroup$ – ryan May 5 '19 at 21:31
  • $\begingroup$ Yes, i have already proved it as np complete. $\endgroup$ – snape May 6 '19 at 5:09
  • $\begingroup$ Yes Apass.Jack that's exactly my intention. $\endgroup$ – snape May 6 '19 at 5:12

Since 3-Colors is NP-Complete, it is also in NP.


$\bullet$ To prove a problem $P$ is in NP, we have to show a polynomial time "yes" certificate

$\bullet$ To prove a problem $P$ is NP-Complete, we have to show: $P \in$ NP and there is another problem $X$ which is NP-Complete, and $X$ can be reduced to $P$.

It is clear then, that:

$P$ is NP-Complete $\Rightarrow P\in$ NP.

The first condition is trivial, and the reduction to 3-SAT is widely known and can be found easily.

| cite | improve this answer | |

Your Answer

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

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