Incomputational complexity theory, asparse language is aformal language (a set ofstrings) such that thecomplexity function, counting the number of strings of lengthn in the language, is bounded by apolynomial function ofn. They are used primarily in the study of the relationship of the complexity classNP with other classes. Thecomplexity class of all sparse languages is calledSPARSE.

Sparse languages are calledsparse because over some finite alphabet${\displaystyle \mathrm{\Sigma }}$ there are a total of${\displaystyle {|\mathrm{\Sigma }|}^n}$ strings of lengthn, and if a language only contains polynomially many of these, then the proportion of strings of lengthn that it contains rapidly goes to zero asn grows. Allunary languages are sparse. An example of a nontrivial sparse language is the set of binary strings containing exactlyk 1 bits for some fixedk; for eachn, there are only${\displaystyle (\genfrac{}{}{0ex}{}{n}{k})}$ strings in the language, which is bounded byn^k.

• SPARSE containsTALLY, the class ofunary languages, since these have at most one string of any one length.

• Although not all languages inP/poly are sparse, there is apolynomial-time Turing reduction from any language inP/poly to a sparse language.^[1]
• Fortune showed in 1979 that if any sparse language isco-NP-complete, thenP =NP.^[2] Mahaney used this to show in 1982 that if any sparse language isNP-complete, thenP =NP (this isMahaney's theorem).^[3] A simpler proof of this based on left-sets was given by Ogihara and Watanabe in 1991.^[4] 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 sparseNP-hard set if and only ifP =NP.^[5]
• Further,E ≠NE if and only if there exist sparse languages inNP that are not inP.^[6]
• There is aTuring reduction (as opposed to theKarp reduction from Mahaney's theorem) from anNP-complete language to a sparse language if and only if${\displaystyle \mathbf{\text{NP}}\subseteq \mathbf{\text{P}}/\text{poly}}$.
• In 1999, Jin-Yi Cai and D. Sivakumar, building on work by Ogihara, showed that if there exists a sparseP-complete problem, thenL =P.^[7]

• Lance Fortnow.Favorite Theorems: Small Sets. April 18, 2006.
• William Gasarch.Sparse Sets (Tribute to Mahaney). June 29, 2007.
• Complexity Zoo:SPARSE

• Formal languages
• Computational complexity theory