Practice problems on Mapping Reducibility

November 13, 2010 1 Comment

Let alphabet set be \Sigma. Given two languages A,B \subseteq \Sigma^*. A is said to be mapping reducible to B if there exists a Turing computable function f s.t. \forall x \in \Sigma^*,~ x \in A \Leftrightarrow f(x) \in B. When A is mapping reducible to B, we denote it as A \leq_m B, A \not \leq_m B otherwise.
In this post I mention a few practice problems on mapping reducibility, a subset of which were posed to the students of ics211 in 2009, Monsoon and cs3105 in 2010, Spring.

Consider the following languages :-

  1. L_1 = \{ < M,w > | M accepts w\}
  2. L_2 = \{ < M > | L(M) \neq \phi \}
  3. L_3 = \{ < M_1,M_2 > | L(M_1) \cap L(M_2) \neq \phi \}
  4. L_4 = \{ < M > | L(M) = \Sigma^{*} \}
  5. L_5 = \{ < M > | L(M) = \{0^{n}1^{n}|n > 0\}\}
  6. L_6 = \{ < M_1,M_2 > | L(M_1)=L(M_2)\}
  7. L_7 = \{ < M_1,M_2 > | L(M_1)=\overline{L(M_2)}\}

In the languages mentioned above M,M_{1},M_{2} donote a Turing Machine.
Prove the following :-

  1. \forall i \in \{1,2,3\} ~ \forall j \in \{1,2,3,4,5,6,7\}, L_i \leq_m L_j.
  2. \forall i,j \in \{4,5,6,7\}, L_i \leq_m L_j.
  3. \forall i \in \{4,5,6,7\} ~ \forall j \in \{1,2,3\}, L_i \not \leq_m L_j.

Filed under puzzle, theoretical computer science

Follow

Get every new post delivered to your Inbox.