Consider the graph coloring problem: given an undirected graph $G$ and a natural number $n$ return yes if we can color the graph with n different colors and no otherwise.

I am able to design a deterministic Turing machine that would solve it with a greedy approach trying the different combinations of coloring with the $n$ colors. I think this takes exponential time although I'm not sure how to proof it.

However, I am not able to conceive a nondeterministic Turing machine that would do so. Can someone guide me designing an algorithm for this machine?

  • $\begingroup$ Are you sure that you know what a non-deterministic Turing machine is? $\endgroup$ Apr 15, 2015 at 18:59
  • $\begingroup$ I guess, a machine that can go in multiple states given a word on the tape? $\endgroup$ Apr 15, 2015 at 19:13
  • $\begingroup$ Something of that sort. $\endgroup$ Apr 15, 2015 at 19:14

1 Answer 1


The algorithm would be as follows:

  1. Go through each vertex and "guess" a coloring using non-determinism. This takes time $O(V\log n)$, since this is the time it takes to write all the colors.
  2. Check that the coloring is legal, which also takes polynomial time. If it's not legal, it rejects, and otherwise it accepts.

By definition, a non-deterministic Turing machine accepts an input if there is some accepting computation path. So the machine accepts iff some valid coloring exists.

  • $\begingroup$ That is what defines NDTM. I don't think this helped - yet. $\endgroup$ Apr 15, 2015 at 19:14
  • 1
    $\begingroup$ On the contrary, this is a complete solution. Of course, it's only a hint, since it's your exercise rather than mine. $\endgroup$ Apr 15, 2015 at 19:17
  • $\begingroup$ Ha! Thanks, I only read before the edit. It is not really homework, but rather self study $\endgroup$ Apr 15, 2015 at 19:18
  • $\begingroup$ where does the $log(n)$ come from? $\endgroup$ Apr 15, 2015 at 19:23
  • 1
    $\begingroup$ It's the number of cells it takes to represent a color. Even this complexity only holds for a multitape machine, since in parallel you also need to count up to $n$ (and up to $V$). $\endgroup$ Apr 15, 2015 at 19:48

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.