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

I read this question Reduction between $\Sigma^*$ and $\emptyset$

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

  • $\begingroup$ What's the definition of $p$? $\endgroup$ – 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.

  • $\begingroup$ 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? $\endgroup$ – ilen Oct 23 '18 at 17:47
  • $\begingroup$ @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$. $\endgroup$ – chi Oct 23 '18 at 18:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.