# Sparse language

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Sparse_language
> Markdown URL: https://mediated.wiki/source/Sparse_language.md
> Source: https://en.wikipedia.org/wiki/Sparse_language
> Source revision: 1351301397
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

In [computational complexity theory](/source/computational_complexity_theory), a '''sparse language''' is a [formal language](/source/formal_language) (a set of [strings](/source/String_(computer_science))) such that the [complexity function](/source/complexity_function), counting the number of strings of length ''n'' in the language, is bounded by a [polynomial](/source/polynomial) function of ''n''. They are used primarily in the study of the relationship of the complexity class '''[NP](/source/NP_(complexity))''' with other classes. The [complexity class](/source/complexity_class) of all sparse languages is called '''SPARSE'''.

All [unary language](/source/unary_language)s 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 <math>\Sigma</math> there are <math>{|\Sigma|}^n</math> 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

== Examples ==
For any fixed integer ''k'', Consider the set of binary strings containing exactly ''k'' repeats of the bit <math>1</math>. For each ''n'', there are only [<math>\binom{n}{k} \lesssim n^k</math>](/source/Binomial_coefficient) strings in the language. Thus it is sparse.

== Relationships to other complexity classes ==

* '''SPARSE''' contains '''TALLY''', the class of [unary language](/source/unary_language)s, since these have at most one string of any one length. 
* '''[E](/source/E_(complexity))''' ≠ '''[NE](/source/NE_(complexity))''' if and only if there exist sparse languages in '''NP''' that are not in '''P'''.<ref>Juris Hartmanis, Neil Immerman, Vivian Sewelson. Sparse Sets in NP-P: EXPTIME versus NEXPTIME. ''Information and Control'', volume 65, issue 2/3, pp.158–181. 1985. [http://portal.acm.org/citation.cfm?id=808769 At ACM Digital Library]</ref>
* If any sparse language is NP-hard with respect to [Turing reductions](/source/Turing_reduction), then ['''PH'''](/source/Polynomial_hierarchy) collapses to <math>\Delta^P_2</math>. This is a consequence of the [Karp–Lipton theorem](/source/Karp%E2%80%93Lipton_theorem).<ref>{{cite book
 | last1 = Karp | first1 = Richard M. | author1-link = Richard M. Karp
 | last2 = Lipton | first2 = Richard J. | author2-link = Richard Lipton
 | editor1-last = Miller | editor1-first = Raymond E.
 | editor2-last = Ginsburg | editor2-first = Seymour
 | editor3-last = Burkhard | editor3-first = Walter A.
 | editor4-last = Lipton | editor4-first = Richard J.
 | contribution = Some connections between nonuniform and uniform complexity classes
 | doi = 10.1145/800141.804678
 | pages = 302–309
 | publisher = ACM
 | title = Proceedings of the 12th Annual ACM Symposium on Theory of Computing, April 28-30, 1980, Los Angeles, California, USA
 | year = 1980}}</ref> This result was improved in 2005, showing that '''PH''' collapses further than <math>\Delta^P_2</math>.<ref>{{Cite journal |last=Cai |first=Jin-Yi |last2=Chakaravarthy |first2=Venkatesan T. |last3=Hemaspaandra |first3=Lane A. |last4=Ogihara |first4=Mitsunori |date=2003 |editor-last=Alt |editor-first=Helmut |editor2-last=Habib |editor2-first=Michel |title=Competing Provers Yield Improved Karp-Lipton Collapse Results |url=https://link.springer.com/chapter/10.1007/3-540-36494-3_47?error=cookies_not_supported&code=d70ac278-1d58-4a8d-ad91-accc309e5cf4 |journal=STACS 2003 |language=en |location=Berlin, Heidelberg |publisher=Springer |pages=535–546 |doi=10.1007/3-540-36494-3_47 |isbn=978-3-540-36494-8|url-access=subscription }}</ref>
*

=== Mahaney's theorem ===
(Fortune, 1979) showed that if any sparse language is ['''co-NP'''-complete](/source/co-NP-complete), then ['''P''' = '''NP'''](/source/P_%3D_NP_problem).<ref>S. Fortune. A note on sparse complete sets. ''SIAM Journal on Computing'', volume 8, issue 3, pp.431–433. 1979.</ref> (Mahaney, 1982) used this to prove [Mahaney's theorem](/source/Mahaney's_theorem) that if any sparse language is ['''NP'''-complete](/source/NP-complete), then '''P''' = '''NP'''.<ref>S. R. Mahaney. Sparse complete sets for NP: Solution of a conjecture by Berman and Hartmanis. ''Journal of Computer and System Sciences'' 25:130–143. 1982.</ref> 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](/source/NP-hard) set if and only if '''P''' = '''NP'''.<ref>{{cite book
| title=Structural Complexity II
| last1=Balcázar
| first1=José Luis
| last2=Díaz
| first2=Josep
| last3=Gabarró
| first3=Joaquim
| year=1990
| isbn=3-540-52079-1
| publisher=[Springer](/source/Springer_Science%2BBusiness_Media)
| pages=130–131}}</ref>

(Ogihara and Watanabe, 1991) gives a simplified proof of Mahaney's theorem based on left-sets.<ref>{{cite journal
 | last1 = Ogiwara | first1 = Mitsunori
 | last2 = Watanabe | first2 = Osamu
 | doi = 10.1137/0220030
 | issue = 3
 | journal = SIAM Journal on Computing
 | mr = 1094526
 | pages = 471–483
 | title = On polynomial-time bounded truth-table reducibility of NP sets to sparse sets
 | volume = 20
 | year = 1991}}</ref>

(Jin-Yi Cai and D. Sivakumar, 1999), building on work by Ogihara, showed that, if there exists a sparse language that is ['''P'''-complete](/source/P-complete) under [logspace (many-one) reduction](/source/Log-space_reduction), then '''[L](/source/L_(complexity))''' = '''[P](/source/P_(complexity))'''.<ref>{{Cite journal |last=Cai |first=Jin-Yi |last2=Sivakumar |first2=D. |date=1999-04-01 |title=Sparse Hard Sets for P |url=https://doi.org/10.1006/jcss.1998.1615 |journal=J. Comput. Syst. Sci. |volume=58 |issue=2 |pages=280–296 |doi=10.1006/jcss.1998.1615 |issn=0022-0000|url-access=subscription }}</ref>

=== P/poly ===
Although not all languages in ['''P'''/poly](/source/P%2Fpoly) are sparse, there is a [polynomial-time Turing reduction](/source/polynomial-time_Turing_reduction) from any language in '''P'''/poly to a sparse language.<ref>[http://www.wisdom.weizmann.ac.il/~oded/CC/mahaney.pdf Jin-Yi Cai. Lecture 11: P=poly, Sparse Sets, and Mahaney's Theorem. CS 810: Introduction to Complexity Theory. The University of Wisconsin–Madison. September 18, 2003 (PDF)]</ref>

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

== References ==

<references />

==External links==
* [Lance Fortnow](/source/Lance_Fortnow). [http://weblog.fortnow.com/2006/04/favorite-theorems-small-sets.html Favorite Theorems: Small Sets]. April 18, 2006.
* [William Gasarch](/source/William_Gasarch). [http://weblog.fortnow.com/2007/06/sparse-sets-tribute-to-mahaney.html Sparse Sets (Tribute to Mahaney)]. June 29, 2007.
* {{CZoo|SPARSE|S#sparse}}

Category:Formal languages
Category:Computational complexity theory

---
Adapted from the Wikipedia article [Sparse language](https://en.wikipedia.org/wiki/Sparse_language) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Sparse_language?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.