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 $?

$\endgroup$

2 Answers 2

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}$.

$\endgroup$
4
  • $\begingroup$ don't understand why $\overline {3SAT} \le_p 3SAT$ as only the opposite is given @Steven $\endgroup$
    – Hjm
    Commented Jan 10, 2023 at 12:40
  • 1
    $\begingroup$ @Hjm for that, use the hint 2 in my answer. $\endgroup$
    – Nathaniel
    Commented Jan 10, 2023 at 13:15
  • $\begingroup$ Is it true that $\overline {\overline {3SAT} } =3SAT$? $\endgroup$
    – Hjm
    Commented Jan 10, 2023 at 13:48
  • $\begingroup$ Yes, by definition of complement. $\endgroup$
    – Steven
    Commented Jan 10, 2023 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}$.

$\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
    Commented Jan 10, 2023 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
    Commented Jan 10, 2023 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
    Commented Jan 10, 2023 at 11:58

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.