# If a problem is complete for NP, is its complement complete for co-NP?

I am trying to prove that for a NP problem that is complete, its complement co-NP should be complete as well.

We know that a decision problem A $$\in$$ NP-complete if a) it is in NP and b) if every other NP problem is polynomial-time many-one reducible to it. There is a similar relationship between co-NP-complete and co-NP problems.

By definition, the complement of a problem is the same decision problem but instead of looking to validate the answer, we are looking to negate it. So it should be "common sense" to say that if a problem is NP-complete, then its complement is co-NP-complete, but how do you prove this? I know it should be easy to prove but I'm out of proofs or ideas.

Let $$L\in \text{NPC}$$. For any $$L' \in \text{coNP}$$ we have $$\overline{L'} \leq_P L$$ and therefore $$L' \leq_P \overline{L}$$ (by the same reduction).