Euclidean field: Difference between revisions
Jump to navigation
Jump to search
Deltahedron (talk | contribs) →Properties: ce |
en>Mark viking →Examples: Added wl |
||
| Line 1: | Line 1: | ||
In [[computational complexity theory]], a '''sparse language''' is a [[formal language]] (a set of [[String (computer science)|strings]]) such that 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 (complexity)|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<sup>''n''</sup> 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 language]]s 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 [[Binomial coefficient|<math>\binom{n}{k}</math>]] strings in the language, which is bounded by ''n''<sup>''k''</sup>. | |||
== Relationships to other complexity classes == | |||
'''SPARSE''' contains '''TALLY''', the class of [[unary language]]s, since these have at most one string of any one length. 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>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. http://www.wisdom.weizmann.ac.il/~oded/CC/mahaney.pdf</ref> Fortune showed in 1979 that if any sparse language is [[co-NP-complete]], then [[P = NP problem|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 used this to show in 1982 that if any sparse language is [[NP-complete]], then P = NP (this is [[Mahaney's theorem]]).<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> A simpler proof of this based on left-sets was given by Ogihara and Osamu in 1991.<ref>M. Ogiwara and O. Watanabe. On polynomial time bounded truth-table reducibility of NP sets to sparse sets. ''SIAM Journal on Computing'' volume 20, pp.471–483. 1991.</ref> '''[[E (complexity)|E]]''' ≠ '''[[NE (complexity)|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> 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 (complexity)|L]]''' = '''[[P (complexity)|P]]'''.<ref>Jin-Yi Cai and D. Sivakumar. Sparse hard sets for P: resolution of a conjecture of Hartmanis. ''Journal of Computer and System Sciences'', volume 58, issue 2, pp.280–296. 1999. ISSN:0022-0000. [http://citeseer.ist.psu.edu/501645.html At Citeseer]</ref> | |||
== References == | |||
<references /> | |||
==External links== | |||
* Lance Fortnow. [http://weblog.fortnow.com/2006/04/favorite-theorems-small-sets.html Favorite Theorems: Small Sets]. April 18, 2006. | |||
* Bill 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]] | |||
Revision as of 21:36, 21 November 2013
In computational complexity theory, a sparse language is a formal language (a set of strings) such that 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 2n 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 strings in the language, which is bounded by nk.
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 P/poly are sparse, there is a 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 co-NP-complete, then P = NP;[2] Mahaney used this to show in 1982 that if any sparse language is NP-complete, then P = NP (this is Mahaney's theorem).[3] A simpler proof of this based on left-sets was given by Ogihara and Osamu in 1991.[4] E ≠ NE if and only if there exist sparse languages in NP that are not in P.[5] 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.[6]
References
- ↑ 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. http://www.wisdom.weizmann.ac.il/~oded/CC/mahaney.pdf
- ↑ S. Fortune. A note on sparse complete sets. SIAM Journal on Computing, volume 8, issue 3, pp.431–433. 1979.
- ↑ 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.
- ↑ M. Ogiwara and O. Watanabe. On polynomial time bounded truth-table reducibility of NP sets to sparse sets. SIAM Journal on Computing volume 20, pp.471–483. 1991.
- ↑ 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. At ACM Digital Library
- ↑ Jin-Yi Cai and D. Sivakumar. Sparse hard sets for P: resolution of a conjecture of Hartmanis. Journal of Computer and System Sciences, volume 58, issue 2, pp.280–296. 1999. ISSN:0022-0000. At Citeseer
External links
- Lance Fortnow. Favorite Theorems: Small Sets. April 18, 2006.
- Bill Gasarch. Sparse Sets (Tribute to Mahaney). June 29, 2007.