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
  • 1
    $\begingroup$ coC is not the complement of C! $\endgroup$
    – Raphael
    Jul 23, 2017 at 10:30

1 Answer 1

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 and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.