$A\leq_p B \iff \bar{A}\leq_p \bar{B}$ (if A is polynomial time reducible to B does that imply that complement of A is polynomial reducible to complement of B)

I was told that this is the case based on the definition of $\leq_p$ but I am having trouble proving this.

  • $\begingroup$ I think the proof differs a bit depending on the type of polytime reduction we're talking about (there are multiple). Could you provide your definition of a polytime reduction? $\endgroup$ – Discrete lizard Mar 16 '18 at 20:10
  • $\begingroup$ @Discretelizard From what I understand a polytime reduction means that we can transform the inputs of A in to the inputs of B in polynomial time $\endgroup$ – Dez Mar 16 '18 at 20:15
  • $\begingroup$ That doesn't sound like a formal definition. Surely whoever told you that 'this is case based on the definition of $\leq_p$' told you what this definition is. (btw, we have MathJax on this site, so everything between '$'-signs renders as mathmode TeX. Please don't use it in titles, though, they are used in places without TeX rendering) $\endgroup$ – Discrete lizard Mar 16 '18 at 20:18
  • $\begingroup$ I was never really given a formal definition, just shown how they were "supposed" to be done. The definition I have been going off is the Many-one reduction found on wikipedia (en.wikipedia.org/wiki/Many-one_reduction) $\endgroup$ – Dez Mar 16 '18 at 20:24
  • 1
    $\begingroup$ 'I was never really given a formal definition' Jikes. I'm sorry to hear that. You did pick the 'right' formalization, though, in the sense that I think this property is relatively simple to prove for that definition. I also think that instead of completely answering this, it is better for you to try it yourself, with some hints. $\endgroup$ – Discrete lizard Mar 16 '18 at 20:38

In case you were wondering, the answer is yes.

Here is the reasoning.

Lemma: Let $f$ be a reduction from $A$ to $B$. Then $f$ is also a reduction from $\overline A$ to $\overline B$.
Proof: By the definition of a reduction, $f$ maps $A$ to $B$ and $f$ maps the complement of $A$ to the complement of $B$. So $f$ maps the complement of the complement of $A$, which is $A$ itself, to $B$, which is the complement of the complement of $B$. By the definition of a reduction again, $f$ is a reduction from the complement of $A$ to the complement of $B$. QED.

Suppose $A$ is polynomial-time reducible to $B$. Let $f$ be a polynomial reduction from $A$ to $B$. The lemmas shows that $f$ is also a reduction from the complement of $A$ to the complement of $B$. Since $f$ is polynomial-time, $\overline A$ is polynomial-time reduced to $\overline B$ by $f$.

With $A$ replaced by $\overline A$ and $B$ by $\overline B$, the above paragraph also shows $\overline A$ is polynomial-time reducible to $\overline B$ implies $A$ is polynomial-time reduced to $B$.

The above two paragraphs shows the equivalence of $A\leq_p B$ and $\overline{A}\leq_p \overline{B}$.

  • $\begingroup$ @Apass.Jack I’ve added some clarifying details. I’m not sure how better to explain it, other than the fact that the if and only if ensures that the complement holds the same relationship. $\endgroup$ – Schemetrical Apr 8 at 1:20
  • $\begingroup$ "f is a polynomial time reduction if and only if a yes instance of B corresponds to a yes instance of f(A)". This statement does not make much sense since f might not be surjective. $\endgroup$ – Apass.Jack Apr 9 at 6:02
  • $\begingroup$ I just took the liberty to revamp this answer, since it does not make sense to write another answer for a simple question like this. $\endgroup$ – Apass.Jack Apr 9 at 6:04
  • $\begingroup$ Your answer is much better, all credit should be yours @Apass.Jack. You’re right that I should have defined f better. Thanks! $\endgroup$ – Schemetrical Apr 9 at 17:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.