# Theory of Complexity - Relation between a class and its complement

i'm in trouble trying to prove the following proposition:

Proposition If $\ C$ is a class closed under reductions and a $\ C$-Complete problem belongs to $\ coC$, then $C=coC$.

Note: $C$ can be any class.

To prove that proposition i thought to split the proof in two ways:

(*): $C \subseteq coC$

I suppose it exists such an $L \in coC$ that is $C$-Complete. For all $L' \in C$ there is a reduction $R : L \rightarrow L'$. Thus $L \in coC$ and $coC$ is closed under reductions (because $C$ is), $L' \in coC$ also, so $C \subseteq coC$.

(*): $coC \subseteq C$

That's the part i'm not able to prove.

Thank you so much.

• coC is not the complement of C! – Raphael Jul 23 '17 at 10:30

The first part is easy since there is a $C$-complete problem that belongs to $coC$ and since all problems in $C$ are reduced to that complete problem, $C \subseteq coC$
As for the second part let $L_C$ be a $C$-complete problem that belongs to $coC$. Then by definition of $coC$, $\overline{L}_C \in C$. So, $\overline{L}_C$ are in $C$ (decidable in $C$). Also since $L_C$ is $C$-complete, for any language $L \in C$ there is a reduction $f$ such as $x \in L \Leftrightarrow f(x) \in L_C$.
Now, if a problem $L \in coC$ then $\overline{L} \in C$ and $x \in \overline{L} \Leftrightarrow f(x) \in L_C$ meaning that $x \in L \Leftrightarrow f(x) \in \overline{L}_C$. So $L$ is reduced to $\overline{L}_C$ which is in $C$. Thus $coC \subseteq C$.