1
$\begingroup$

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
$\endgroup$
1
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Thanks, so for the first one what is FP ? $\endgroup$ – tala Feb 11 '20 at 0:36
  • 1
    $\begingroup$ The class off all functions that can be completed in polynomial time $\endgroup$ – narek Bojikian Feb 11 '20 at 8:57

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.