Assuming $\Sigma  = \{  0, 1\}$..Given a language $L$, such that for each $n\in \mathbb{N}$ we have $n$ words of length $n$ in $L$ and assuming $L\in NP$, can we prove also that $L\in Co-NP$?So it is the same as showing that $\overline{L}\in NP$, but I'm not really sure on how to prove this.Does anyone have an idea?
Are the complements of $NP$-languages with only $n$ words of length $n$ also in $NP$?
complexity theory;closure properties;np
Hint: Suppose we are given a word $w$ of length $n$ which is not in $L$, and let $w_1,\ldots,w_n$ be the words of length $n$ which are in $L$. A witness that $w \notin L$ is the list $w_1,\ldots,w_n$ (all different from $w$!) together with witnesses that $w_1,\ldots,w_n \in L$.