3
$\begingroup$

Given two languages $L_1$ and $L_2$ that are in $\mathsf{P}$, can it be proven that there is a polynomial time reduction from $L_1$ to $L_2$ and vice versa? If so, how?

I noticed that if $L_1$ is the empty language, and $L_2$ is the "full language" $\{ 0,1 \}^*$, there does not seem to be a reduction from $L_2$ to $L_1$, but this is not clear to me. I know how a reduction works, so that is not a problem for me.

$\endgroup$
  • 3
    $\begingroup$ That's actually an interesting edge case that I hadn't spotted, but usually for these sorts of problems we ignore these edge cases $\emptyset$ and $\Sigma^*$. Can you recall the definition of a reduction? $\endgroup$ – ymbirtt Dec 31 '13 at 22:37
  • $\begingroup$ L1 <= L2 if there exists a reduction function f such that for all input X, X is part of L1 IFF f(X) is part of L2. $\endgroup$ – Yechiel Labunskiy Dec 31 '13 at 22:40
  • $\begingroup$ See here. Also, brushing up on fundamentals might help. $\endgroup$ – Raphael Jan 3 '14 at 14:05
7
$\begingroup$

No, in general

As you've already noticed, if $L_2$ is either the full language or the empty language, there can be no reduction from $L_1$ to $L_2$ - the argument is simple enough.

Recall the definition. $L_1$ reduces to $L_2$ iff there exists a function $f: \Sigma^* \rightarrow \Sigma^*$ such that $\forall w \in L_1, f(w) \in L_2$, and $\forall w \notin L_1, f(w) \notin L_2$, and $f$ is computable in polynomial time.

Suppose $L_1 \neq \emptyset$ and $L_2 = \emptyset$. Suppose also that some function $f$ exists such that $w \in L_1 \implies f(w) \in L_2$. This argument immediately gives us a contradiction. We know that $w \in L_1$ can be true, but $f(w) \in \emptyset$ can never be true, so there cannot be such an $f$, poly-time or not.

The argument for $L_2 = \Sigma^{*}$ is similar.

There are some other subtleties floating around this question, and it's a worthwhile exercise to think of all the possible combinations you could get from assigning $L_1$ and $L_2$ to $\emptyset$, $\Sigma^{*}$ and some non-empty non-"full" language.

This said, with a further assumption, there's a small trick we can apply to make this argument hold:

Yes, if we have that neither $L_1$ nor $L_2$ are empty or "full"

Both $L_1$ and $L_2$ are in $P$, so we can decide them in polynomial time.

Let $w_\top \in L_2$ and $w_\bot \notin L_2$. These words are constant, so are of constant length.

We will define $f$ as follows. If $w \in L_1$, then $f(w)=w_\top$. If $w \notin L_1$, then $f(w)=w_\bot$. Clearly, $f$ represents a reduction from $L_1$ to $L_2$ according to the above definition. Since $L_1$ can be decided in polynomial time, we can compute $f$ in polynomial time.

So $f$ is a poly-time reduction from $L_1$ to $L_2$. This argument can work the other way to provide a reduction from $L_2$ to $L_1$, so the languages reduce to each other.

If exactly one of $L_1$ or $L_2$ is empty or "full", we can reduce from one to the other. Which way? Why?

$\endgroup$
  • $\begingroup$ Thanks for your help, a bit fudgy in my mind, but starting to sink in. $\endgroup$ – Yechiel Labunskiy Dec 31 '13 at 22:55
  • $\begingroup$ ymbirtt, Normally we try not to just dump the complete answer to a question that looks like a homework exercise, especially when the question shows no evidence of effort. (It might be what the original author is hoping for, but I don't think it's doing them a service, and I don't think it's good for our community in the long run -- it just encourages more such bad questions.) I tend to think it is better to provide hints, or better still, wait for the original author to make a serious effort on their own and come back to show us what they've tried. $\endgroup$ – D.W. Dec 31 '13 at 22:59
  • 1
    $\begingroup$ $\Sigma^*$ and $\emptyset$ are valid languages in $P$. They are not trivial cases. So the answer is actually NO. This answer needs to be edited to be more complete. $\endgroup$ – Auberon Feb 20 '17 at 15:48
  • 1
    $\begingroup$ @Auberon, yep, you're right! Damn, I was sloppy 3 years ago, wasn't I? I'll throw an updated version together momentarily. $\endgroup$ – ymbirtt Feb 21 '17 at 8:27
  • 2
    $\begingroup$ "No in general" is a rather misleading way of saying "Yes, except in two special cases." $\endgroup$ – David Richerby Feb 21 '17 at 9:17

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.