0
$\begingroup$

Can you please explain to me why the following is true?

Ιf 3SAT reduces to its complement then NP=coNP.

Thoughts: 3SAT is NP-complete so for every X in NP

$X \leq 3SAT$

$\overline {3SAT} $ is NP-complete so for every Y in coNP

$Y \leq \overline {3SAT} $

So, $X \leq 3SAT \leq \overline {3SAT}$

But don't we have to also prove that

$Y \leq 3SAT $?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

For $A \in \mathsf{NP}$ you have $ A \le_p 3SAT \le_p \overline{3SAT} \in \mathsf{co{\text -}NP}$, which implies $A \in \mathsf{co{\text -}NP}$ and hence $\mathsf{NP} \subseteq \mathsf{co{\text -}NP}$.

Simmetrically, for $A \in \mathsf{co{\text -}NP}$, you have $A \le_p \overline{3SAT} \le_p 3SAT \in \mathsf{NP}$, which implies $A \in \mathsf{NP}$ and hence $\mathsf{co{\text -}NP} \subseteq \mathsf{NP}$.

From $\mathsf{NP} \subseteq \mathsf{co{\text -}NP} \subseteq \mathsf{NP}$, it follows that $\mathsf{NP} = \mathsf{co{\text -}NP}$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ don't understand why $\overline {3SAT} \le_p 3SAT$ as only the opposite is given @Steven $\endgroup$
    – Hjm
    Jan 10 at 12:40
  • 1
    $\begingroup$ @Hjm for that, use the hint 2 in my answer. $\endgroup$
    – Nathaniel
    Jan 10 at 13:15
  • $\begingroup$ Is it true that $\overline {\overline {3SAT} } =3SAT$? $\endgroup$
    – Hjm
    Jan 10 at 13:48
  • $\begingroup$ Yes, by definition of complement. $\endgroup$
    – Steven
    Jan 10 at 14:56
0
$\begingroup$

Hint 1: $Y\in \text{co}\mathsf{NP}$ if and only if $\overline{Y}\in\mathsf{NP}$.

Hint 2: $A\leqslant B$ if and only if $\overline{A}\leqslant \overline{B}$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ If I use hint 1: $3SAT \in coNP$ (because $3SAT \leq \overline {3SAT}$) so $\overline {3SAT} \in NP $and so every Y in coNp is also in NP? $\endgroup$
    – Hjm
    Jan 10 at 11:26
  • $\begingroup$ While the result would be what we want to obtain, the process is not quite it. I used the notation $Y$ to represent any problem $Y$ in $\text{co}\mathsf{NP}$, like in your post. $\endgroup$
    – Nathaniel
    Jan 10 at 11:41
  • $\begingroup$ I don't get what I have done wrong, can you help me? I suposse that I have to start with an $L \in coNP $ and so that it also belongs to NP. $\endgroup$
    – Hjm
    Jan 10 at 11:58

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.