¿Podemos usar la misma reducción L1 -> L2 para COL1 -> COL2
-
29-09-2020 - |
Pregunta
hace l1 ≤ pag L2 ceder ese col1 ≤ pag COL2 por la misma reducción?
Solución
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. $
Licenciado bajo: CC-BY-SA con atribución
No afiliado a cs.stackexchange