CS4123 Theory of Computation. A99
Homework 3

Prof. Carolina Ruiz
Department of Computer Science
Worcester Polytechnic Institute

Homework 3

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


  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: Show that the Traveling Salesperson problem belongs to NP.

Additional Problems for students taking this course for graduate credit:

  1. Problem 7.7 from the textbook.
  2. Problem 7.20 from the textbook.
  3. Problem 7.37 from the textbook.