# Is it decidable whether one language is polytime reducible to another?

Let $$L_1$$ and $$L_2$$ be two decision problems.

Is there an algorithm deciding whether $$L_1 \leq_P L_2$$, that is, whether $$L_1$$ is reducible to $$L_2$$ in polynomial time?

• How are $L_1$ and $L_2$ given to the algorithm? – Yuval Filmus Dec 4 '18 at 4:54
• Elaborate the possible permutations of, decidable, undecidable languages anf Polynomial time and Non-deterministic polynomial time algirithms. – CHETAN RAJPUT Dec 4 '18 at 6:03
• I don't see how this answers my question. At any rate, once you pose your question in a well-defined way, the answer will likely be that the problem is undecidable. – Yuval Filmus Dec 4 '18 at 6:04
• I guess then i didn't get your question, if you can eleborate more , i can add it. – CHETAN RAJPUT Dec 4 '18 at 7:17
• The input to an algorithm has to be finite. Decision problems are infinite objects. You can't given a decision problem as an input. Therefore I find it hard to understand your question. – Yuval Filmus Dec 4 '18 at 7:25

I'm going to assume that your question is whether the language $$L = \{\langle M_1\rangle; \langle M_2\rangle\mid L(M_1)\leq_\mathrm{p} L(M_2)\}$$ is decidable, where $$\langle M\rangle$$ is the description of Turing machine $$M$$ and $$\leq_\mathrm{p}$$ denotes polynomial-time many-one reducibility.

This language is undecidable.

The only language that is many-one reducible to $$\Sigma^*$$ is $$\Sigma^*$$ itself. This is because a many-one reduction from $$X$$ to $$\Sigma^*$$ must, by definition, map all "no" instances of $$X$$ to "no" instances of $$\Sigma^*$$. However, $$\Sigma^*$$  has no "no" instances, so the reduction can only exist if $$X$$ also has no "no" instances, i.e., if $$X=\Sigma^*$$.

So, now let $$Y$$ be any Turing machine that accepts every input. The language $$H=\{\langle M\rangle\mid \langle M\rangle;\langle Y\rangle\in L\}$$ is clearly reducible to $$L$$. But $$H$$ is the language of Turing machines that accept every input, which is undecidable.

• A good explanation. May be I couldn't able to ask properly but expecting this kind of explanation. Thanx. – CHETAN RAJPUT Dec 4 '18 at 12:53

Let $$L_2$$ be some easy to decide language. For example,

$$L_2 = \{ \omega : |\omega| \equiv 0 \mod 2 \}$$

Then reducing instances of $$L_1$$ to instances of $$L_2$$ is as hard as deciding $$L_1$$ itself, and your question boils down to:

Given a description of a TM halting on every input, can you simulate it in polynomial time?

This is undecidable, which you can prove by the same argument as for the Halting problem.