COL1 - > COL2には同じ縮小L1 - > L2を使用できますか

Question

L1にします ≤ p L2 そのCOL1を降伏する ≤ p Col2は同じ減少について？

Answer 1

はい。 $ f $ の場合、 $ x \ in l_1 \ iff f（x）\ inのような多項式時間計算可能関数です。L_2 $

$ x \ in \ text {co} l_1 \ iff x \ not \ in l_1 \ iff f（x）\ not \ in l_2 \ iff f（x）\ in\ text {co} l_2。 $