Cheap and Secure Web Hosting Provider : See Now

# [Solved]: Non-deterministic vs Deterministic turing machine to solve graph colouring

, ,
Problem Detail:

For graph coloring decision problem I mean the following: given a undirected graph, \$G\$, we have \$GCDP(G, n)\$. This returns yes instance is given if it we can color the graph with n different colors.

I am able to construct a deterministic turing machine, that would take exponential time. This machine would have a greedy approach and try the different combinations of coloring, given \$n\$ colors. (However, I am not able to determine, how I can prove this is exponential)

However, I am not able to concieve a non deterministic machine that would do so. Would I not use the same strategy for the deterministic machine?

Can someone guide me designing an algorithm for this machine?

#### Answered By : Yuval Filmus

Hint: The non-deterministic Turing machine guesses a coloring using \$n\$ colors and then verifies that it is a legal coloring.

How do you implement this? The machine goes over all vertices in turn, and "guesses" a coloring (using non-determinism); guessing a coloring takes time \$O(V\log n)\$, since this is the time it takes to write all the colors. Then it checks that the coloring is legal, which also takes polynomial time. If it's not legal, it rejects, and otherwise it accepts. According to the definition, a non-deterministic machine accepts an input if there is some accepting computation path. So the machine accepts iff some valid coloring exists.