Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer
I have a dreadful mistake. I thought your problem has a simple solution, but now I see I had a mistake. Therefore, I have no idea if it is possible to prove that L is NP-hard in this case. What is the source of the question? –  Gadi A Jun 9 '11 at 14:09

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.