Reduction Theorem in TOC
Reduction Theorem :
A reduction from A to B is a function
f : Ξ£1* β Ξ£2* such that For any w β Ξ£1*, w β A if f(w) β B
- Every w β A maps to some f(w) β B.
- Every w β A maps to some f(w) β B.
- f does not have to be injective or surjective.
Why Reductions Matter?
If language A reduces to language B, we can use a recognizer / co-recognizer / decider for B to recognize / co-recognize / decide problem A.
If A is reducible to B ( A<= B ) β
- Problem A is easily reducible to Problem B that clearly states that β the problem βBβ is at least as hard as problem βAβ.
OR
- βx, x β A, if f(x) β B; where f is many to one reduction from A to B, which is denoted as ( A <=m B ).
- A <= B β Problem A is reducible to problem B.
- A <=m B β Problem A is many to one reducible to problem B.
- A <=m B β Problem A is reducible in polynomial manner to problem B.
Mapping Reductions :
- A function f : Ξ£1* β Ξ£2* is called a mapping reduction from A to B if For any w β Ξ£1*, w β A if(w) β B.
- f is a computable function.
- Intuitively, a mapping reduction from A to B says that a computer can transform any instance of A into an instance of B such that the answer to B is the answer to A.
Properties of Reduction :
- If A<=B, and A is undecidable then B is also undecidable.
- If A<=B, and B is undecidable then A need not to be undecidable.
- If A<=B, and A is decidable then B need not to be undecidable.
- If A<=B, and B is decidable then A is also decidable.
- If A<=B, and B is recursive then A is also recursive.
- If A<=B, and A is recursive then B need not to be recursive.
- If A<=B, and B is recursive enumerable then A is also recursive enumerable.
- If A<=B, and A is recursive enumerable then B need not to be recursive enumerable.
- If A<=B, and B is P-problem then A is also P-problem.
- If A<=B, and A is P-problem then B need not to be P-problem.
- If A<=B, and B is NP-problem then A is also NP-problem.
- If A<=B, and A is P-problem then B need not to be P-problem.
- If A<=B and B<=P then A<=P (transitivity).
- If A<=B and B<=A then A and B are polynomial equivalent.
- If A<=B and A is not REL then B is also not REL.
- If A<=B, and A is not P-problem then B is also not P-problem.
- If A<=B and A is not recursive problem then B is also not recursive problem.
Examples β
1. A : t4 β 1 ββββ- B : t2 β 1 , C : t2 + 1
In example 1 since A is solvable and B,C<A so, B and
C is also solvable
since, ( t4 - 1 )= ( t2 - 1 ) * ( C : t2 + 1 )
2. A : Is L(D) = Ξ£* ? βββ> Problem A can be reduced to B : Is L(D1) = Ξ£* β L(D2) ?
In example B is subset of A so A is reduced to Problem B.
3. A : Is L(G) = NULL ? βββ> Problem A can be reduced to B : Is L(G1) is subset of L(G2) ?
If above problem A is reduced to a simpler form problem B then solution would be easy.
4. A : a3 + b3 + 3a2b + 3b2a --------------> A is reduced to B : ( a + b )3 If A reduces to B and B is βsolvable,β then A is βsolvable.β
5. Reduction of LD to ββββ-> 0* 1*
Wyes =01 and Wno= 10
Then reduced form f(w) will be : f (w)={ 01 if w β LD , 10 if w β LD }
6. Find reduced grammar equivalent to grammar G, having production rules
P : S --> AC | B, A --> a, C --> c | BC, E --> aA | e
Phase 1 - T= {a ,c, e}, W1= {A,C,E}, W2= {A,C,E,S}, W3= {A,C,E,S} G' = { (A,C,E,S), (A,C,E), P, (s) }, P: S --> AC , A --> a, C --> c, E --> aA | e Phase 2 - Y1= {S} , Y2 = {S,A,C} , Y3= {S, A, C, a, c} , YL1 = { S, A, C, a, c } G'' = { (A,C,S), (a,c), P, {S} }, P: S --> AC , A --> a, C --> c
7. Problem A (Hard Problem) β Move from New Guinea to Amazon City.
( Since, we know there is an easy way from New Guinea to Canada) So, we will reduce the problem into easier one.
Problem B(easier problem) β Move from Canada to Amazon City.
So, It is clear if we can find a solution to the easier problem, then we can use it to solve a harder one.
8. Given Problem A : L1<=L2 and L2<=L3 β
- If L2 is decidable then ββ> L1 is decidable and L3 is either decidable or not decidable.
- If L2 is undecidable then ββ> L1 is either decidable or not decidable and L3 is undecidable .
Contact Us