Teorema de reducción en TOC

Teorema de reducción:
una reducción de A a B es una función             

• Todo w ∈ A corresponde a algún f(w) ∈ B.
• Todo w ∉ A corresponde a algún f(w) ∉ B.
• f no tiene que ser sobreyectiva o sobreyectiva.

¿Por qué son importantes las reducciones?
Si la lengua A se reduce a la lengua B, podemos usar un reconocedor/co-reconocedor/decisor para que B reconozca/co-reconozca/decida el problema A.

Si A es reducible a B ( A<= B ) –

• El problema A es fácilmente reducible al problema B que establece claramente que el problema ‘B’ es al menos tan difícil como el problema ‘A’.

                                                                                               

                                                                                           O
 

• ∀x, x ∈ A, si f(x) ∈ B; donde f es una reducción de muchos a uno de A a B, que se denota como ( A <= _m B ) .

1. A <= B – El problema A es reducible al problema B.
2. A <=m B – El problema A es muchos a uno reducible al problema B.
3. A <=m B – El problema A es reducible en forma polinomial al problema B.

Reducciones de mapeo:

• Una función f : Σ1* → Σ2* se llama reducción de mapeo de A a B si Para cualquier w ∈ Σ1*, w ∈ A si (w) ∈ B.
• f es una función computable.
• Intuitivamente, una reducción de mapeo de A a B dice que una computadora puede transformar cualquier instancia de A en una instancia de B tal que la respuesta a B sea la respuesta a A.

Propiedades de reducción:

• Si A<=B, y A es indecidible, entonces B también es indecidible.
• Si A<=B, y B es indecidible, entonces A no necesita ser indecidible.
• Si A<=B, y A es decidible, entonces B no necesita ser indecidible.
• Si A<=B, y B es decidible, entonces A también es decidible.
• Si A<=B, y B es recursivo, entonces A también es recursivo.
• Si A<=B, y A es recursivo, entonces B no necesita ser recursivo.
• Si A<=B, y B es enumerable recursivo, entonces A también es enumerable recursivo.
• Si A<=B, y A es enumerable recursivamente, entonces B no necesita ser enumerable recursivamente.
• Si A<=B, y B es un problema P, entonces A también es un problema P.
• Si A<=B, y A es un problema P, entonces B no necesita ser un problema P.
• Si A<=B, y B es un problema NP, entonces A también es un problema NP.
• Si A<=B, y A es un problema P, entonces B no necesita ser un problema P.
• Si A<=B y B<=P entonces A<=P (transitividad).
• Si A<=B y B<=A entonces A y B son polinomios equivalentes.
• Si A<=B y A no es REL, entonces B tampoco es REL.
• Si A<=B, y A no es un problema P, entonces B tampoco es un problema P.
• Si A<=B y A no es un problema recursivo, entonces B tampoco es un problema recursivo.

Ejemplos –

1. A : t ^{4 – 1 ————- B : t2 – 1 , C : t2 + 1} 
En el ejemplo 1 dado que A es solucionable y B,C<A entonces, B y 
C también son solucionables 

 since, ( t4 - 1 )= ( t2 - 1 ) * ( C : t2 + 1 ) 

2. A: ¿L(D) = Σ*? ———> El problema A se puede reducir a B : ¿Es L(D1) = Σ* – L(D ₂₎ ? 
En el ejemplo, B es un subconjunto de A, por lo que A se reduce al problema B.

3. A: ¿Es L(G) = NULO? ———> El problema A se puede reducir a B: ¿L(G1) es un subconjunto de L(G2)? 
Si el problema A anterior se reduce a un problema B de forma más simple, la solución sería fácil.

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. Reducción de L _D a ————-> 0* 1*
    W _si =01 y W _no = 10
    Entonces la forma reducida f(w) será : f (w)={ 01 si w ∈ L _D  , 10 si w ∉ L _D }

6. Encuentre la gramática reducida equivalente a la gramática G, que tenga reglas de producción 

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. Problema A (problema difícil): mudarse de Nueva Guinea a Amazon City.
    (Ya que sabemos que hay una manera fácil de Nueva Guinea a Canadá) Entonces, reduciremos el problema a uno más fácil.

    Problema B (problema más fácil): muévase de Canadá a Amazon City.
     Entonces, está claro que si podemos encontrar una solución al problema más fácil, entonces podemos usarla para resolver uno más difícil.

8.   Dado el problema A: L ₁ <=L ₂ y L ₂ <=L ₃ –

1. Si L ₂ es decidible entonces —–> L ₁ es decidible y L ₃ es decidible o no decidible.
2. Si L ₂ es indecidible entonces —–> L1 es decidible o no decidible y L3 es indecidible.