¿Podemos usar la misma reducción L1 -> L2 para COL1 -> COL2

Question

hace l1 ≤ pag L2 ceder ese col1 ≤ pag COL2 por la misma reducción?

Answer 1

si.Si $ f $ es una función computable de tiempo polinomial de modo que $ x \ en l_1 \ iff f (x) \ enL_2 $ luego

$ x \ in \ texto {co} l_1 \ iff x \ no \ in l_1 \ iff f (x) \ no \ in l_2 \ iff f (x) \ en\ texto {co} l_2. $