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. 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 \Sigma there are ^n 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

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 \Sigma there are ^n 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 (Fortune, 1979) showed that if any sparse language is co-NP-complete, then P = NP. (Mahaney, 1982) used this to prove Mahaney's theorem that if any sparse language is NP-complete, then P = NP. 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. (Ogihara and Watanabe, 1991) gives a simplified proof of Mahaney's theorem based on left-sets. (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. ==External links== Lance Fortnow. Favorite Theorems: Small Sets. April 18, 2006. William Gasarch. Sparse Sets (Tribute to Mahaney). June 29, 2007.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1351301397 under CC BY-SA 4.0; modifications have been made.