Podemos usar a mesma redução L1 -> L2 para Col1 -> Col2

Question

faz l1 ≤ P. L2. rendimento que col1. ≤ P. COL2 para a mesma redução?

Answer 1

sim.Se $ F $ é uma função computacional de tempo polinomial tal que $ x \ em l_1 \ iff f (x) \ inL_2 $ então

$ x \ in \ text {co} l_1 \ iff x \ não \ in l_1 \ iff f (x) \ não \ in l_2 \ iff f (x) \ in\ text {CO} L_2. $