Podemos usar a mesma redução L1 -> L2 para Col1 -> Col2
-
29-09-2020 - |
Pergunta
faz l1 ≤ P. L2. rendimento que col1. ≤ P. COL2 para a mesma redução?
Solução
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. $
Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange