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$ – Yuval Filmus Apr 15 '15 at 18:59
  • $\begingroup$ I guess, a machine that can go in multiple states given a word on the tape? $\endgroup$ – revisingcomplexity Apr 15 '15 at 19:13
  • $\begingroup$ Something of that sort. $\endgroup$ – Yuval Filmus Apr 15 '15 at 19:14

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$ – revisingcomplexity Apr 15 '15 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$ – Yuval Filmus Apr 15 '15 at 19:17
  • $\begingroup$ Ha! Thanks, I only read before the edit. It is not really homework, but rather self study $\endgroup$ – revisingcomplexity Apr 15 '15 at 19:18
  • $\begingroup$ where does the $log(n)$ come from? $\endgroup$ – revisingcomplexity Apr 15 '15 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$ – Yuval Filmus Apr 15 '15 at 19:48

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.