polynomial reduction & co np complete

Question

I would like to know how we can demonstrate these two problems :

• $A \leqslant_p B$ implies $\overline A \leqslant_p \overline B$
• The complement of 3-SAT is co-NP-complete

Answer 1

For the first one, since $A \leq_p B$, there must exist a function $f \in \operatorname{FP}$, such that $x \in A$ if and only if $f(x) in B$ for an arbitrary word $x$. We can prove that $f$ is also a reduction from $\overline A$ to $\overline B$ as follows: Let x be an arbitrary word. \begin{align} x \in \overline A &\iff\\ x \notin A &\iff\\ f(x) \notin B &\iff\\ f(x) \in \overline B&\\ &\qquad\square \end{align}

Now for the second part, we know that 3-SAT is NP-complete. For a given language $A \in \operatorname{co-NP}$, let $B = \overline A$. Clearly $B \in \operatorname{NP}$ and hence, there is a reduction from $B$ to 3-SAT. As proven above, the same reduction is a reduction from $A$ to the complement of 3-SAT.