# polynomial reduction & co np complete

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

## 1 Answer

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.

• Thanks, so for the first one what is FP ?
– tala
Commented Feb 11, 2020 at 0:36
• The class off all functions that can be completed in polynomial time Commented Feb 11, 2020 at 8:57