Encyclopedia

Sparse language

Wikipedia contributorsAdapted for Fathomly · View authors

2 min read
Source updated April 27, 2026

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 ${|\Sigma |}^{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

01Examples

For any fixed integer k, Consider the set of binary strings containing exactly k repeats of the bit $1$ . For each n, there are only ${\binom {n}{k}}\lesssim n^{k}$ strings in the language. Thus it is sparse.

02Relationships to other complexity classes

SPARSE contains TALLY, the class of unary languages, since these have at most one string of any one length.
E ≠ NE if and only if there exist sparse languages in NP that are not in P.
If any sparse language is NP-hard with respect to Turing reductions, then PH collapses to $\Delta _{2}^{P}$ . This is a consequence of the Karp-Lipton theorem. This result was improved in 2005, showing that PH collapses further than $\Delta _{2}^{P}$ .

Mahaney's theorem

(Fortune, 1979) showed that if any sparse language is co-NP-complete, then P = NP. (Mahaney, 1982) used this to prove Mahaney's theorem that if any sparse language is NP-complete, then P = NP. Mahaney's argument does not actually require the sparse language to be in NP (because the existence of an NP-hard sparse set implies the existence of an NP-complete sparse set), so there is a sparse NP-hard set if and only if P = NP.

(Ogihara and Watanabe, 1991) gives a simplified proof of Mahaney's theorem based on left-sets.

(Jin-Yi Cai and D. Sivakumar, 1999), building on work by Ogihara, showed that, if there exists a sparse language that is P-complete under logspace (many-one) reduction, then L = P.

P/poly

Although not all languages in P/poly are sparse, there is a polynomial-time Turing reduction from any language in P/poly to a sparse language.

There is a Turing reduction (as opposed to the Karp reduction from Mahaney's theorem) from an NP-complete language to a sparse language if and only if ${\textbf {NP}}\subseteq {\textbf {P}}/{\text{poly}}$ .

Watch videos about Sparse languageExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Sparse language”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.