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 <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> strings in the language. Thus it is sparse.
== Relationships 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'''.<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, then '''PH''' collapses to <math>\Delta^P_2</math>. This is a consequence of the Karp–Lipton 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, then '''P''' = '''NP'''.<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 that if any sparse language is '''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 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 | 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 under logspace (many-one) reduction, then '''L''' = '''P'''.<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 are sparse, there is a 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 (as opposed to the 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. [http://weblog.fortnow.com/2006/04/favorite-theorems-small-sets.html Favorite Theorems: Small Sets]. April 18, 2006. * 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