Can we use the same reduction L1 -> L2 for coL1 -> coL2
-
29-09-2020 - |
Question
does L1 ≤ p L2 yield that coL1 ≤ p coL2 for the same reduction?
Solution
Yes. If $f$ is a polynomial-time computable function such that $x \in L_1 \iff f(x) \in L_2$ then
$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. $
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange