Können wir die gleiche Reduktion l1 -> l2 für col1 -> col2 verwenden
-
29-09-2020 - |
Frage
macht l1 ≤ P. L2. Rendite dieser Col1. ≤ P. Col2 für die gleiche Reduzierung?
Lösung
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. $
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit cs.stackexchange