#### Complexity Questions

Please see the attachment as the pdf copy causes format loss 3. (2 points) Let L be the class of languages that can be decided by a two-tape deterministic TM with a read-only input tape (so the input tape cannot be modified) and using at most O(log(n)) cells on the second tape (the work tape), where n is the length of the input. Show that L âŠ† P. 4. (2 points) Show that if P = NP, then every language in P except âˆ… and Î£âˆ— is NPcomplete. 5. (2 points) A k-coloring of an undirected graph is an assignment of one of k colors to each vertex of the graph such that no edge is incident to vertices of the same color. If there is such an assignment of colors to the vertices of a graph, we call the graph k-colorable. Let k-COLORABLE be the language of undirected graphs that are k-colorable. It is known that 2-COLORABLE âˆˆ P and 3-COLORABLE is NP-complete. (It would be a good idea to look up the proof that 3-COLORABLE is NP-complete.) (a) Show that k-COLORABLE is NP-complete for all k > 3. (b) Consider the following scheduling problem. You are given a list of sports events E1, …, Ei to be scheduled and a list of athletes A1, …, Aj . Each athlete is participating in some specified subset of these events. You must schedule these events into slots so that no athlete has two events in the same time slot. The problem is to determine if such a schedule exists that uses only k slots. Formulate this problem as a language and show that this language is NP-complete.