Possiamo usare la stessa riduzione L1 -> L2 per COL1 -> COL2

Question

fa l1 ≤. P. L2. cedere che col1. ≤. P. COL2 per la stessa riduzione?

Answer 1

Sì.Se $ f $ è una funzione calcolabile in poligomatico in modo tale da $ x \ in l_1 \ IFF F (X) \ INL_2 $ quindi

$ x \ in \ text {co} l_1 \ iff x \ non \ in l_1 \ IFF f (x) \ non \ in l_2 \ IFF F (X) \ IN\ testo {co} l_2. $