Question

does L1 ≤ p L2 yield that coL1 ≤ p coL2 for the same reduction?

Was it helpful?

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
scroll top