Polynomial Reduction for restriction

Question

I ran across a polynomial reduction that used the fact that one language was a restriction of the other. Is that statement really true? $$ L_1 \subseteq L_2 \rightarrow L_2 \leq_{p} L_1 $$

Thanks!

Answer 1

The claim in the question is false.

Every language contains the empty language as a subset ($\emptyset \subseteq L_2$) but the only languages that are polynomial time Turing reducible to the empty set ($L_2 \leq_p \emptyset$) are the ones that are decidable in polynomial time.

Similarly, every language is a subset of the language that includes every word ($L_2 \subseteq \Sigma^*$) but the only languages that are polynomial-time Turing reducible to $\Sigma^*$ (so $L_2 \leq_p \Sigma^*$) are the ones that are decidable in polynomial time.

There are similar issues if we are talking about polynomial-time many-one reducibility - the empty language and $\Sigma^*$ are also exceptional cases.

The claim in the original source could still be correct, if it uses other information that was in context there and which wasn't included here.