Questions
1. State whether the following statements are true or not. You must give a BRIEF explanation or show a counter example to receive full credit.
(a) If a language L is decidable then the language L is also decidable.
(b) Every deterministic Turing machine (DTM) has an equivalent nondeterministic Turing machine.
(c) There exists a polynomial-time reduction from Boolean Satisfiability Problem (SAT) to Subset Sum Problem (SS).
(d) If a problem P is NP-complete then the language induced by problem P is undecidable.
2. (20pts) Give a Turing Machine that decides language L = {wln : l'ild = n, w E {0, 1}1.
3. (30pts) Disprove (by reduction) or prove that the following languages are decidable.
(a) L = {(A) : A is a DFA and L(A) = L'(A)} where L' (A) = {7.1) : w E L(A)}
(b) L = {(A, S) : A is a TM and L(A) C S}
(c) L = {(M1, M2) : M1 and M2 are TMs such that M1 accepts (M2) and M2 accepts (M1)}
4. (30pts) Number 3 is a lucky number (this is the reason why you have 3 assignments). So, we have two problems (both are related with number "3"): 3-SET-PARTITION and 3-GRAPH-PARTITION. Prove that they are NP-Complete.
(a) 3-SET-PARTITION: Let A, B, C be three finite, disjoint sets and let T be a subset of A x B x C. That is, T consists of triples (a, b, c) such that a E A, b E B and c E C. Given A, B, C, T and an integer k, the 3-SET-PARTITION problem decides whether there is a subset M of T (i.e., M C T), such that I* > k and for any two distinct triples (ai, b1, ci) E M and (a2, b2, c2) E M, we have al a2, bi b2 and ci c2.
(b) 3-GRAPH-PARTITION: Given an undirected graph G = (V, E), the 3-GRAPH-PARTITION problem decides whether the vertex set V can be partitioned into three disjoint subsets 3/4_, V2 and V3, such that for any two vertices va E V and vb E V, if (va, vb) E E, then va and vb cannot be placed into the same partition Vi, i E {1, 2, 3}.