Does coNP-completeness imply NP-hardness? In particular, I have a problem that I have shown to be coNP-complete. Can I claim that it is NP-hard? I realize that I can claim coNP-hardness, but I am not sure if that terminology is standard.
I am comfortable with the claim that if an NP-complete problem belonged to coNP, then NP=coNP. However, these lecture notes state that if an NP-hard problem belongs to coNP, then NP=coNP. This would then suggest that I cannot claim that my problem is NP-hard (or that I have proven coNP=NP, which I highly doubt).
Perhaps, there is something wrong with my thinking. My thought is that a coNP-complete problem is NP-hard because:
- every problem in NP can be reduced to its complement, which will belong to coNP.
- the complement problem in coNP reduces to my coNP-complete problem.
- thus we have a reduction from every problem in NP to my coNP-complete, so my problem is NP-hard.