Lesson plan
Sparse language
In computational complexity theory, a sparse language is a formal language (a set of strings) such that the complexity function, counting the number of strings of length n in the language, is bounded by a polynomial function of n. They are used primarily in the study of the relationship of the complexity class NP with other classes. The complexity class of all sparse languages is called SPARSE. All unary languages are sparse, trivially. Consequently, the concept of sparse language is usually only used for languages with at least 2 letters. Sparse languages are called sparse because over some finite alphabet \Sigma there are ^n strings of length n. So, when the language is not unary, the probability of a uniformly randomly sampled length-n string belongs to the language converges exponentially to 0
Article summary
In computational complexity theory, a sparse language is a formal language (a set of strings) such that the complexity function, counting the number of strings of length n in the language, is bounded by a polynomial function of n. They are used primarily in the study of the relationship of the complexity class NP with other classes. The complexity class of all sparse languages is called SPARSE. All unary languages are sparse, trivially. Consequently, the concept of sparse language is usually only used for languages with at least 2 letters. Sparse languages are called sparse because over some finite alphabet \Sigma there are ^n strings of length n. So, when the language is not unary, the probability of a uniformly randomly sampled length-n string belongs to the language converges exponentially to 0
Key claims
No claims recorded.
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
No sources recorded.
Key claims and bibliography are generated from the same tracked claims and sources as the article page.