If a language is a NP-hard, is also its complement NP-hard?

Question

I was asked the next question:

L is a language which |L (conjunction) {0,1}|=1. In other words, the number of words with length n is exactly one. I need to prove that if L is NP-Hard, also its complement is NP-hard.

The GENERAL question: When I solves it, I remarked that I have a verification algorithm for L and witness y. I suggest to run y on A, and answer the opposite. This will be the verification algorithm for the complement language. But is this always true, for all languages?

What did I miss? What this language is differ? Thanks a lot.

Answer 1

Note that NP-hard means "every language in NP is reducible to it" and not "is in NP", and so talking about "verification algorithm" and "witness" is irrelevant.

"Your" language is different in the sense that given a reduction to L, it can be transformed quite easily into a reduction to the complement of L, relying heavily (very heavily) on the "1 word of every length" property of L. Give it another thought without going into the general question.

Now for the general question. In general this is an open question; for NP-complete languages it is exactly the question of whether $NP=coNP$. If $P=NP$ then indeed $NP=coNP$, and hence, proving that $NP\ne coNP$ is "at least as hard as proving $P\ne NP$", so we don't expect an answer soon (the belief is that $NP\ne coNP$).

It is interesting to note that for space complexity, we have an equality for most classes (one need the amount of memory to be at least logarithmic). This is the famous Immerman–Szelepcsényi theorem.