9
$\begingroup$

In order to prove that 3-coloring is decidable, is it sufficient to say:

  • Each node in the graph has 3 possible colors
  • Therefore we can enumerate over all $3^n$ possibilities and then check that no two edges connect nodes with the same color

Does that prove that 3-coloring is decidable? Or do I need to construct a Turing machine for a proper proof?

By 3-coloring I'm talking about the graph coloring problem; i.e. assign one of 3 colors to each node in an undirected graph such that no two adjacent nodes have the same color.

|cite|improve this question
$\endgroup$
  • 5
    $\begingroup$ This is good enough for me. By the way, even if you want to be very formal you don't have to provide a Turing machine; a program in any Turing-complete language will suffice. (Indeed, the language need not even be Turing-complete, we just need it to define computable functions.) $\endgroup$ – Yuval Filmus Jan 1 '16 at 20:53
  • $\begingroup$ For most people it does. In an introductory course it might not. Also, for some people "formal proof" means something different, which you might have seen if you took a course on logic. $\endgroup$ – Yuval Filmus Jan 1 '16 at 21:52
  • $\begingroup$ @YuvalFilmus Thanks. What does a "formal proof" in the context of a logic course look like, would you be able to point me to an example please? $\endgroup$ – Jenny Jan 2 '16 at 3:19
  • $\begingroup$ @Jenny If you're interested, take a logic course. $\endgroup$ – Yuval Filmus Jan 2 '16 at 11:56
  • $\begingroup$ @YuvalFilmus I don't have access to a logic course, is there a book or an online source you can recommend? $\endgroup$ – Jenny Jan 2 '16 at 13:01
10
$\begingroup$

It depends entirely on what level of formality you're aiming for. The informal description of an algorithm in your question is quite enough to convince me that 3-colourability is decidable. If you wanted to be a bit more formal, you could give pseudocode. If you wanted to be more formal still, you could describe a Turing machine in English. If you wanted to be even more formal, you could write down the full description of the Turing machine and prove that it really does decide 3-colourability.

Having said that, of the options I've listed, it's way more likely that there'd be an error in the description of the Turing machine or in its correctness proof! So it's not clear which proof would be the most believable.

|cite|improve this answer
$\endgroup$
-5
$\begingroup$

All the non deterministical problems for TM are decidable, so from your description you demonstrated you needed $ 3^{n}$ turing machines to validate a solution. So your explanation is enough.

|cite|improve this answer
$\endgroup$
  • 2
    $\begingroup$ Hi, welcome to CS. Unfortunately, your post doesn't seem to answer the question meaningfully. $\endgroup$ – vonbrand Jan 2 '16 at 2:50

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.