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?


closed as unclear what you're asking by Shaull, FrankW, David Richerby, Wandering Logic, Yuval Filmus Oct 14 '14 at 19:23

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

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