Pouvons-nous utiliser la même réduction L1 -> L2 pour COL1 -> COL2
-
29-09-2020 - |
Question
fait l1 ≤ p L2 Rendez ce col1 ≤ p Col2 pour la même réduction?
La solution
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. $
Licencié sous: CC-BY-SA avec attribution
Non affilié à cs.stackexchange