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.

Sparse languages are called sparse because there are a total of 2ⁿ strings of length n, and if a language only contains polynomially many of these, then the proportion of strings of length n that it contains rapidly goes to zero as n grows. All unary languages are sparse. An example of a nontrivial sparse language is the set of binary strings containing exactly k 1 bits for some fixed k; for each n, there are only ${\displaystyle {\binom {n}{k}}}$ strings in the language, which is bounded by n^k.

Relationships to other complexity classes

• SPARSE contains TALLY, the class of unary languages, since these have at most one string of any one length.

• Although not all languages in
  polynomial-time Turing reduction from any language in P/poly to a sparse language.^[1]
• Fortune showed in 1979 that if any sparse language is
  NP-hard set if and only if P = NP.^[5]
• Further, E ≠ NE if and only if there exist sparse languages in NP that are not in P.^[6]
• There is a
  Karp reduction
  from Mahaney's theorem) from an NP-complete language to a sparse language if and only if ${\displaystyle {\textbf {NP}}\subseteq {\textbf {P}}/{\text{poly}}}$.
• In 1999, Jin-Yi Cai and D. Sivakumar, building on work by Ogihara, showed that if there exists a sparse P-complete problem, then L = P.^[7]

References