Possiamo usare la stessa riduzione L1 -> L2 per COL1 -> COL2
-
29-09-2020 - |
Domanda
fa l1 ≤. P. L2. cedere che col1. ≤. P. COL2 per la stessa riduzione?
Soluzione
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. $
Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a cs.stackexchange