### 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).

2. (10 points) Consider the complement of this language:
ETMC = { < M > | M is a Turing machine and L(M) != the empty set}.

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:

• Given: A graph G=(V,E).
• Output: "Yes", if there is 2-coloring of the vertices in V (i.e. a coloring of the graph that uses only 2 different colors). "No", otherwise

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:

• Given: Two sequences w1, w2, ... wn and p1, p2, ... pn of non-negative numbers and two numbers W and P.
• Output:"Yes", if there is a subset J of {1,2,...,n} so that (sumi in J wi) <= W and (sumi in J pi) >= P. "No", otherwise.

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:

• Given: An undirected graph G=(V,E) and an integer k.
• Output:"Yes", if there is an independent set of vertices with at least k vertices in G (An independent set of vertices in G is a subset V' of V so that no two vertices in V' are joined by an edge in E). "No", otherwise.

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