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?

  • $\begingroup$ How are $L_1$ and $L_2$ given to the algorithm? $\endgroup$ – Yuval Filmus Dec 4 '18 at 4:54
  • $\begingroup$ Elaborate the possible permutations of, decidable, undecidable languages anf Polynomial time and Non-deterministic polynomial time algirithms. $\endgroup$ – CHETAN RAJPUT Dec 4 '18 at 6:03
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Dec 4 '18 at 6:04
  • $\begingroup$ I guess then i didn't get your question, if you can eleborate more , i can add it. $\endgroup$ – CHETAN RAJPUT Dec 4 '18 at 7:17
  • $\begingroup$ 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. $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ A good explanation. May be I couldn't able to ask properly but expecting this kind of explanation. Thanx. $\endgroup$ – 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.

| cite | improve this answer | |

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.