Prove/ Disprove

claim

For language L s.t L satisfies pumping lemma with pumping constant $ℓ$ ,
$L | | L$ satisfies pumping lemma with pumping constant $2 ℓ$

Proposition 1

$RE$ is not closed under complement

Proposition 2

$c o RE$ is closed under intersection.

Proposition 3

$R$ is closed under Kleene star.

Proposition 4

$RE$ is closed under Prefix, but $R$ is not closed under Prefix,

Prove: If $L_{1} \leq_{m} L_{2}$ and $L_{2} \leq_{m} L_{3},$ then $L_{1} \leq_{m} L_{3} .$
Disprove: If $L_{1} \leq_{m} L_{2}$ and $L_{2} \leq_{m} L_{1},$ then $L_{1} = L_{2} .$
Disprove: If $L_{1} \subseteq L_{2}$ then $L_{1} \leq_{m} L_{2} .$
Disprove: For every $L_{1}, L_{2}$ , then $L_{1} \leq_{m} L_{2}$ or
Prove: If $L$ is regular, then $L \leq_{m} H A L T$
For every nontrivial $L_{1}, L_{2} \in P, L_{1} \leq L_{2}$ TRUE
For every nontrivial $L_{1}, L_{2} \in N P, L_{1} \leq_{P} L_{2}$ Equivalent to an Open Problem
There exists a language in $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 N P$ is decidable by a deterministic TM in time $n^{O (\log n)}$ . TRUE.