1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ coC is not the complement of C! $\endgroup$ – Raphael Jul 23 '17 at 10:30
1
$\begingroup$

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

$\endgroup$

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.