Prove/ Disprove
For language L s.t L satisfies pumping lemma with pumping constant \(\ell \) ,
\(L||L\) satisfies pumping lemma with pumping constant \(2\ell \)
\(\mathcal{RE}\) is not closed under complement
\(co\mathcal{RE}\) is closed under intersection.
\(\mathcal{R}\) is closed under Kleene star.
\(\mathcal{RE}\) is closed under Prefix, but \(\mathcal{R}\) is not closed under Prefix,
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. \)
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.\)
Disprove: If \(\mathcal{L}_1 \subseteq \mathcal{L}_2\) then \( \mathcal{L}_1 \leq _m \mathcal{L}_2.\)
Disprove: For every \(\mathcal{L}_1,\mathcal{L}_2\), then \(\mathcal{L}_1 \leq _m \mathcal{L}_2\) or
Prove: If \(\mathcal{L}\) is regular, then \(\mathcal{L} \leq _m HALT\)
For every nontrivial \(L_1,L_2\in P, L_1\le L_2\) TRUE
For every nontrivial \(L_1,L_2\in NP, L_1\le _P L_2\) Equivalent to an Open Problem
There exists a language in \( \mathcal{RE}\) that is complete w.r.t polynomial-time reductions. TRUE.
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.