Homework Assignments

From Introduction to the Theory of Computation by Michael Sipser, PWS Publishing unless otherwise noted.

1.4 (c, f & l)
1.5 (b, c)
For any language L, subset of Sigma*, define HALF(L) as follows:
HALF(L) = { x in Sigma* | there exists y in Sigma*, |x| = |y| and xy is in L }.
Show that if L is regular, then HALF(L) must also be regular.

5.10
5.14 & 5.15
Prove directly that the following language is undecidable (i.e., don't use Rice's Theorem).
L₁₇ = { i | L(M_i) contains exactly 17 strings },
where M_i is the ith Turing Machine in the canonical list of Turing Machines.
Optional: Show that L₁₇ is not Turing recognizable.

5.20
5.21
A set is cofinite if it is the complement of a finite set. Let
COF = { < M > | M is a TM and L(M) is cofinite}
FIN = { < M > | M is a TM and L(M) is finite}
Prove that FIN ≤_m COF. That is FIN reduces to COF via a many-one reduction (a.k.a. a "mapping" reduction).

6.5
6.17
Prove directly that A_TM ≤_m-reduces to FIN and the complement of A_TM ≤_m-reduces to FIN, where:
FIN = { < M > | M is a TM and L(M) is finite}

Prove that Dominating Set is NP-complete by showing that Vertex Cover reduces to Dominating Set via a polynomial-time many-one reduction, where
VC = { < G, k > | G = (V,E) is an undirected graph and there exists a subset V' of V with |V'| <= k such that for each edge (u,v) in E either u or v is in V' }

DOM = { < G, k > | G = (V,E) is an undirected graph and there exists a subset V' of V with |V'| <= k such that for each vertex u in V - V' there exists v in V' such that (u,v) is in E.
Construct a logspace transducer that takes as input an undirected graph encoded as a list of edges and outputs the same graph encoded as an adjacency matrix.
8.19

Last modified: 22 Jul 2024 11:31:05 EDT by Richard Chang, chang@umbc.edu