6
$\begingroup$

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?

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

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ That is what defines NDTM. I don't think this helped - yet. $\endgroup$
    – revisingcomplexity
    Commented 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$
    – Yuval Filmus
    Commented 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$
    – revisingcomplexity
    Commented Apr 15, 2015 at 19:18
  • $\begingroup$ where does the $log(n)$ come from? $\endgroup$
    – revisingcomplexity
    Commented 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$
    – Yuval Filmus
    Commented 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.