NP problem

6. (a) Briefly define the concept of a polynomial time reduction XPY between problems X 1 mark] (b) Fix a number k. Let k-COLOR be the following problem. Given an undirected graph G, can we assign at most k colors to the vertices of G so that no adjacent vertices have the same and Y color? Show that 3-COLOR SP 4-COLOR. (3 marks] (c) Explain how one can use the concept of polynomial time reducibility to show indirectly that [I mark] a problem is intractable. 6. (a) Briefly define the concept of a polynomial time reduction XPY between problems X 1 mark] (b) Fix a number k. Let k-COLOR be the following problem. Given an undirected graph G, can we assign at most k colors to the vertices of G so that no adjacent vertices have the same and Y color? Show that 3-COLOR SP 4-COLOR. (3 marks] (c) Explain how one can use the concept of polynomial time reducibility to show indirectly that [I mark] a problem is intractable