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 there are 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

This article is issued from Wikipedia. The text is available under Creative Commons Attribution-Share Alike 4.0 unless otherwise noted. Additional terms may apply for the media files.