CS4123 Theory of Computation. A99
Homework 3
Homework 3
Due on Tuesday, October 5, 1999 at the beginning of class (9:00 p.m.)
Problems:
 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.
 Problem 7.31 of the textbook.

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.
 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 NPcomplete,
just that it is in NP).
 Consider the Traveling Salesperson problem:
 Given:
 A set of n cities {c1,...,cn},
 an integer k, and
 a set of
n(n1)/2 distances {d_1,2, d_1,3, ..., d_1,n, d_2,3, ..., d_2,n, d_n1,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(n1),in + d_in,i1 of the
cicle satisfies l <= k.
Show that the Traveling Salesperson problem belongs to NP.
Additional Problems for students taking this course for graduate
credit:
 Problem 7.7 from the textbook.
 Problem 7.20 from the textbook.
 Problem 7.37 from the textbook.