L-complement in NP

Question

Let L be a language s.t. for every natural n, the number of words of length n in L is n.
The alphabet is {0,1}.
And let's assume that L is NP. Why L-complement is also in NP?

Answer 1

If it is known a-priori that L has the property that there are exactly n words of length n in L, then your statement follows. In fact, this works for any polynomial amount of words in L. In other words, if we allow there to be poly(n) words in L with poly(n) known a-priori, the idea still works. To see this, note that to find all words of length n is L is also in NP since there is a polynomial number of them.

To see if s in {0,1}* is in L-complement, just form the certificate for all words of length |s|, and see if s is one of the words. If s is one of the words, then of course, s is in L, and if s is not one of the words, s is in L-complement.

Answer 2

Since L is in NP it is decidable (recursive) and so is its complement L'. Now, L' may or may not be in NP. But we are given that for any string length n, exactly one string belong to L, which means for any string length all but one string belong to L'.

Now, definition of NP says that all "yes" instances of the problem can be solved in polynomial time using a nondeterministic TM. So, given an instance of , we non-deterministically take all words of length n, where n is the length of w, and see if it is in L. As soon as we get the word (such a word is sure to exist as exactly one word of length n belong to L), we see if this word is same as x. If it is not same (and only if it is not same), x in L' and we get this answer in polynomial time making L' an NP problem.