0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\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.