Let $L \in NP$ such that $|L \cap \{0,1\}^n|=\operatorname{poly}(n)$ for all $n$. Prove that $L \in \mathrm{co\text{-}NP}$.
If I understand the problem correctly, in words this says that "for any $n$, the number of strings of length $n$ in $L$ is a polynomial of $n$." I have no idea how this helps me to prove that $\overline L \in \mathrm{NP}$. The only thing I could think of is for each input $x$ for $\overline L$, go through all words of length $|x|$ in $L$ (there are only $\operatorname{poly}(x)$ of those), and see if $x$ is one of them or not.
The obvious problem with this solution is first, that I don't think it's possible to simply iterate through those specific words - even finding them could theoretically take exponential time. And second, this doesn't use the fact that $L \in \mathrm{NP}$. Quite the opposite - it proves $\overline L \in \mathrm{P}$ and therefore $L \in \mathrm{P}$.
A push in the right direction would be appreciated!
I'm going to assume the number is exactly $poly(n)$.
The proof certificate for $L^C$ is the list of all words of length $n$ which are in $L$ with their proof certificates. To check whether $x \not\in L$ against the proof certificate, first check that the number of strings in the certificate is exactly $poly(n)$, then for each string in the certificate check whether its proof certificate is valid, and then that $x$ is not one of the strings. This takes at most a polynomial number of steps.