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

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

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

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

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

• 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?
– Hjm
Jan 10 at 11:26
• 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. Jan 10 at 11:41
• 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.
– Hjm
Jan 10 at 11:58