CS4123 Theory of Computation
Homework 4 - B 2002
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.
- (20 points) Consider the language E_{TM}:
E_{TM} = { < 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).
- (10 points) Is E_{TM} semi-decidable? Prove your answer.
- (10 points) Consider the complement of this language:
E_{TM}^{C} = { < M > | M is a Turing machine and L(M) != the empty set}.
Is E_{TM}^{C} semi-decidable? Prove your answer.
- (20 points) Prove that the following language DECIDER_{TM} over Sigma is undecidable:
DECIDER_{TM} = { < 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.
- (20 points) Prove that the following language LESSTHAN10_{TM} over Sigma is undecidable:
LESSTHAN10_{TM} = { < 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.
- (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.
- (20 points) Consider the 0-1 knapsack problem:
- Given: Two sequences
w_{1},
w_{2}, ...
w_{n}
and
p_{1},
p_{2}, ...
p_{n}
of non-negative numbers and two numbers W and P.
- Output:"Yes", if there is a subset J of {1,2,...,n} so that
(sum_{i in J} w_{i}) <= W and
(sum_{i in J} p_{i}) >= P.
"No", otherwise.
- (8 points) Show that this problem is in the class NP.
- (12 points) Show that this problem is NP-complete.
Hint: Construct a reduction from the Partition problem
(see Homework 4 from A term 1999).
- (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.
- (8 points) Show that this problem is in the class NP.
- (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
You can submit this homework assignment in any of the following ways. Make
sure you hand it in BY 4:30 pm on Monday, December 9th.
- by handing in your solutions during class on Monday, December 9th.
- by handing in your solutions during my office hour on Monday,
December 9th, 2-3 pm.
- by leaving your solutions in my mailbox (CS office FL233) before the deadline.
PLEASE MAKE
SURE YOU LEAVE YOUR SOLUTIONS IN **MY** MAILBOX (the one UNDER the arrow
marked with my lastname RUIZ).