Prove/ Disprove

claim

For language L s.t L satisfies pumping lemma with pumping constant \(\ell \) ,
\(L||L\) satisfies pumping lemma with pumping constant \(2\ell \)

Proposition 1

\(\mathcal{RE}\) is not closed under complement

Proposition 2

\(co\mathcal{RE}\) is closed under intersection.

Proposition 3

\(\mathcal{R}\) is closed under Kleene star.

Proposition 4

\(\mathcal{RE}\) is closed under Prefix, but \(\mathcal{R}\) is not closed under Prefix,

  1. Prove: If \(\mathcal{L}_1 \leq _m \mathcal{L}_2\) and \(\mathcal{L}_2 \leq _m \mathcal{L}_3, \) then \( \mathcal{L}_1 \leq _m \mathcal{L}_3. \)

  2. Disprove: If \(\mathcal{L}_1 \leq _m \mathcal{L}_2\) and \(\mathcal{L}_2 \leq _m \mathcal{L}_1, \) then \( \mathcal{L}_1 = \mathcal{L}_2.\)

  3. Disprove: If \(\mathcal{L}_1 \subseteq \mathcal{L}_2\) then \( \mathcal{L}_1 \leq _m \mathcal{L}_2.\)

  4. Disprove: For every \(\mathcal{L}_1,\mathcal{L}_2\), then \(\mathcal{L}_1 \leq _m \mathcal{L}_2\) or

  5. Prove: If \(\mathcal{L}\) is regular, then \(\mathcal{L} \leq _m HALT\)

  6. For every nontrivial \(L_1,L_2\in P, L_1\le L_2\) TRUE

  7. For every nontrivial \(L_1,L_2\in NP, L_1\le _P L_2\) Equivalent to an Open Problem

  8. There exists a language in \( \mathcal{RE}\) that is complete w.r.t polynomial-time reductions. TRUE.

  9. If there exists a deterministic TM that decides SAT in time \(n^{O(\log n)}\)
    Then every \(L\in NP\) is decidable by a deterministic TM in time \(n^{O(\log n)}\). TRUE.