Pouvons-nous utiliser la même réduction L1 -> L2 pour COL1 -> COL2

Question

fait l1 ≤ p L2 Rendez ce col1 ≤ p Col2 pour la même réduction?

Answer 1

Oui.Si $ f $ est une fonction calculable de temps polynomial telle que $ x \ in l_1 \ iff f (x) \ inL_2 $ alors

$ x \ in \ text {co} l_1 \ iff x \ pas \ in l_1 \ iff f (x) \ pas \ in l_2 \ iff f (x) \ in\ Text {CO} L_2. $