WPI Worcester Polytechnic Institute

Computer Science Department
------------------------------------------

CS4123 Theory of Computation 
Homework 4 - B 2002

PROF. CAROLINA RUIZ 

Due Date: Part 1: Problems 1, 2, 3, and 4 due Monday, Dec. 9 by 4:30 pm
Part 2: Problems 5 and 6 due Tuesday, Dec. 10 by 4:30 pm 
Help session: Thursday Dec. 5, 3:00-4:00 pm in FL232
AND Friday Dec. 6, 11:30 am -12:30 pm in the CS Annex

------------------------------------------

Problems

This homework consists of 6 problems, 20 points each, for a total of 120 points. The homework is worth 100 points and the remaining 20 are extra credit points.
  1. (20 points) Consider the language ETM:
    ETM = { < M > | M is a Turing machine and L(M) = the empty set}.
    This language is undecidable (See Theorem 5.2 on pages 173-174, and Quiz 2).

    1. (10 points) Is ETM semi-decidable? Prove your answer.
    2. (10 points) Consider the complement of this language:
      ETMC = { < M > | M is a Turing machine and L(M) != the empty set}.
      Is ETMC semi-decidable? Prove your answer.

  2. (20 points) Prove that the following language DECIDERTM over Sigma is undecidable:

    DECIDERTM = { < M > | M is a decider (i.e. M is a Turing machine and M halts on each and every input)}.
    That is, prove that the problem of given a Turing machine M determining whether M halts on all inputs is undecidable.

  3. (20 points) Prove that the following language LESSTHAN10TM over Sigma is undecidable:

    LESSTHAN10TM = { < M > | M is a Turing machine and L(M) contains less than 10 words}.
    That is, prove that the problem of given a Turing machine M determining whether |L(M)| < 10 is undecidable.

  4. (20 points) A coloring of a graph is an assignment of colors to its vertices so that no two adjacent vertices are assigned the same color. Consider the 2-colorability problem:

    Show that this problem is in the class P. That is, show that there is a deterministic Turing machine that decides this problem in polynomial time in the size of the input.


  5. (20 points) Consider the 0-1 knapsack problem:

    1. (8 points) Show that this problem is in the class NP.
    2. (12 points) Show that this problem is NP-complete.
      Hint: Construct a reduction from the Partition problem (see Homework 4 from A term 1999).


  6. (20 points) Consider the Independence Set problem:

    1. (8 points) Show that this problem is in the class NP.
    2. (12 points) Show that this problem is NP-complete.

Additional Problem for Students taking the course for Graduate Credit

None this time. Just do your best on the problems above.


Homework Submission