Lets have an arbitrary complexity class $C$.

Does $C$-complete = co-$C$-complete imply that $C$ = co-$C$?

I think that the answer is yes, but I am not sure whether my reasoning is correct. I tried to prove it like this:

Let $L$ be a $C$-complete language, so all problems in $C$ are polynomially many-to-one reducible to it. If $L \in C$ and $\bar{L} \in C$, then $C-complete = co-C-complete$ (because all complements of problems in co-$C$ are reducible to both $L$ and $\bar{L}$). That implies that $C = co-C$ so $C$ is closed under complement.

Is this a correct approach?

  • 1
    $\begingroup$ Yes, you seem to have solved your problem. What's the question? $\endgroup$ – Shaull Oct 14 '14 at 17:50
  • $\begingroup$ I was looking for some kind of confirmation that my solution is correct... because I was not sure about that... $\endgroup$ – Smajl Oct 14 '14 at 21:48

Browse other questions tagged or ask your own question.