# Homework 3

Due on Tuesday, October 5, 1999 at the beginning of class (9:00 p.m.)

#### Problems:

1. Analyze the time complexity of the Turing machine M1 on p. 127 of the textbook, which decides the language B = {w#w | w belongs to {0,1}*}. Note that the size of the input w#w is equal to 2*(size of w) + 1.

2. Problem 7.31 of the textbook.

3. Show that every regular language can be decided in linear time. In other words, show that if L is a regular language, there is a decider M_L that, given a word w of size n, takes O(n) time to decide whether or not the word w belongs to L.

4. Consider the 3Color problem described in problem 7.34. Show that the 3Color problem is in NP. (You don't need to show that the problem is NP-complete, just that it is in NP).

5. Consider the Traveling Salesperson problem:
• Given:
• A set of n cities {c1,...,cn},
• an integer k, and
• a set of n(n-1)/2 distances {d_1,2, d_1,3, ..., d_1,n, d_2,3, ..., d_2,n, d_n-1,n} between the n cities.
• Answer: "Yes", if there is a cicle {ci1, ..., cin} of the cities such that the length l = d_i1,i2 + d_i2,i3 + .... + d_i(n-1),in + d_in,i1 of the cicle satisfies l <= k.
Show that the Traveling Salesperson problem belongs to NP.