# is This reduction possible?

If we have $$L \in p$$ and $$L' \neq \emptyset$$ and , $$L' \neq \Sigma^*$$ . is $$L \leq^p L'$$ ?

Maybe this question is irrelevant to my question, but I'm little seconfused.

• What's the definition of $p$? – Sebastian Oberhoff Oct 23 '18 at 12:49

If $$L \in p$$, then we can define the reduction function by cases as follows
$$f(x) = \begin{cases} g(x) & \mbox{if x\in L} \\ h(x) & \mbox{if x\notin L} \end{cases}$$
where $$g,h$$ are functions in the same class $$p$$. Indeed, under such premises, $$f$$ also belongs to class $$p$$: it can be computed by first testing whether the input $$x$$ belongs to $$L$$, and then computing $$g(x)$$ or $$h(x)$$ accordingly. Both of these computation steps belong to class $$p$$.
If $$L'$$ is not trivial, we can fix a point $$y_0 \notin L'$$ and a point $$y_1 \in L'$$, and then let $$g(x)=y_1$$ and $$h(x)=y_0$$. Since these are constant functions, they are trivial to compute, so they belong to any reasonable class $$p$$.
You can now verify that $$x\in L \iff f(x)\in L'$$, proving that $$f$$ is indeed a reduction.
• Hi @chi , thanks a lot! For $f(x) \in L'$ then $x \in L$ , we use $g(x)=y_1 \in L'$ , am I right? – ilen Oct 23 '18 at 17:47
• @ilen Yes. The point is, by definition of $f$, $f(x)$ is either $y_0$ or $y_1$. The former happens only when $x\in L$, the latter only when $x\notin L$. – chi Oct 23 '18 at 18:03