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 Answer 1

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, 2020 at 0:36
  • 1
    $\begingroup$ The class off all functions that can be completed in polynomial time $\endgroup$ Feb 11, 2020 at 8:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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