Können wir die gleiche Reduktion l1 -> l2 für col1 -> col2 verwenden

Question

macht l1 ≤ P. L2. Rendite dieser Col1. ≤ P. Col2 für die gleiche Reduzierung?

Answer 1

ja.Wenn $ F $ eine polynomialzeitige Berechnungsfunktion ist, so dass $ X \ in L_1 \ IFF F (x) \ inL_2 $ dann

$ x \ in \ text {co} l_1 \ iff x \ nicht \ in l_1 \ iff f (x) \ nicht \ in l_2 \ iff f (x) \ in\ text {co} l_2. $