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.