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?

Improve this question
$\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$
    – David Richerby
    Sep 7, 2018 at 16:33

1 Answer 1

Reset to default
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$.

Improve this answer
$\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$
    – Jesus is Lord
    Jul 29, 2018 at 20:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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