reducibility

Question

given a decidable language L1 and some other language L2.
can we decide whether L2 is reducible to L1? is the problem decidable?

Answer 1

Property : S is a subset of RE and it represents and contains a subest of RE languages which obeys a particular behaviour or property. And one of the possible property is as follows :

$L \text{ is reducible to } L_1$ where $L \in \text{SET of all RE languages }$

Property Language : $L_P = \left \{ L | L \text { is reducible to } L_1 \right \}$ where $L_1$ has a TM decider.

• S is not empty because clearly $L_1 \in S$
• And there are semi-decidable languages inside the RE domain which are not a part of the property set S
• => S is neither $\phi$ nor it contains all RE
• => $\emptyset \subset P\subset RE$

 So, S is non-trivial property. From Rices theorem, $L_P$ is undecidable.

Link Property Language and Rice Theorem

Comments

@Kapil @Debasish

One thing tell me, we can prove like this

L1 is decidable.

L2 is unknown problem

L2 is reducable to L1

means L2 is more harder than L1.

So, L2 satisfies greater range than L1

So, L2 must be undecidable.

Is it correct approach for this solution?

---

L2 is reducable to L1

means L2 is more harder than L1. wrong ..it should be L1 is at least hard as L2

So, L2 satisfies greater range than L1

So, L2 must be undecidable.

Is it correct approach for this solution? You are considering one possible language L2,,but the required language is all such set of L2, we need L2 checker machine. That machine we need to find , is it computable machine or not.

Like regular TM : means regular language checker machine : This machine is not computable. 

I hope you got the difference between a language and a language checker

---

@Debasish

not getting clearly the difference between a language and a language checker

Answer 2

In  my opinion , it is decidable to conclude whether L2 is reducible to L1 or not.U can see the link :

https://en.wikipedia.org/wiki/Reduction_(complexity)

Reduction of one problem to another is nothing but transforming one problem to another.

If L2 <_m L1 it means that if an algorithm exists for solving L1 efficiently , then it can be used as a subroutine to find whether L2 can be solved efficiently.Now we are given L1 is decidable , meaning there exists an algorithm for language(or problem) L1.Now if using this algorithm we are able to solve L2 efficiently , this means L1 is reducible to L2 else not reducible.

So we are able to conclude the reducibilty of L2 into L1 . Hence it should be a decidable problem i.e. we are able to decide whether L2 is reducible to L1.

Secondly for any 2 languages s.t. L2 <_m L1 so these 3 categories of languages(easy languages) work from right to left i.e. if right one is known we can conclude about left one :

a) If L1 is P , L2 is P.(But converse is not necessarily true)

b) If L1 is NP , L2 is NP.

c) If L1 is decidable ,  L2 is decidable.

Using the point c) , we can conclude that L2 is decidable as well. 

Comments

@Motamarri Anusha,

Take a case, for instance, 

Do set of all TM's in this world are reducible to aⁿbⁿ ? I dont think so, implying non trivial property in the sense of rice theorem .

OR we can modify your problem to this =>

{ ⟨ M ⟩ |  L(M) is context free } is surely non trivial and hence undecidable .

---

@kapilp
yes i agree with you

---

@sushant...seen today only.sorry.

• Given $\large L_2 \leq_m L_1$ (how reduction was done don't worry, not our business)
• What do we need ?
• Property P: Reducible to $L_1$
• Given a whole bunch of RE languages, among them, we need to say which one obeys P
• That is we need a language checker, machine that checks property P in a language and tells YES and NO.
• Is there any automated version of this particular checker exists? NO. (rice theorem)

Answer 3

given that L1 is decidable language  and   L2 is reducible to L1   so we know that  if L1 is decidable then L2 is also decidable via move backwords support decidable, p-problem, NP problem, REC ,RE except NPH, undecidable. so finally it is decidable