1
$\begingroup$

A language $L$ is said to be sparse if there exist a polynomial $p$ such that $|L \cap \{0,1\}^n| \le p(n)$.

One trivial example is suppose language is over single alphabet $1$ then $$L = \{1^n | n \in Z^+\}$$

Question : What are the other non-trivial examples of sparse languages?

$\endgroup$
1
  • 1
    $\begingroup$ I don't really understand what you're looking for. Any class that meets the definition is an example, so what's stopping you from generating your own examples? $\endgroup$ Sep 7 '18 at 16:33
5
$\begingroup$

I don't think that there exists a reasonable characterization of all sparse languages (for instance, it's trivial to define sparse languages that sit arbitrarily high on the arithmetical hierarchy).

However, since $\{0,1\}^*$ has exponential growth, you need to be able to derive some kind of combinatorial property from the language definition. For example, let $k$ be a constant and consider the following language:

$\qquad L = \{x \mid x \text{ contains $k$ ones}\}$

$L$ is sparse, the key observation being that $\binom{n}{k}$ for a fixed $k$ is a polynomial in $n$.

$\endgroup$
1
  • $\begingroup$ I understand the example, I think: n^k is the polynomial, right? However I'm confused by "some kind of combinatorial property". Can you explain that more? $\endgroup$ Jul 29 '18 at 20:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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