•
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. • If any sparse language is NP-hard with respect to
Turing reductions, then
PH collapses to \Delta^P_2. This is a consequence of the
Karp–Lipton theorem. This result was improved in 2005, showing that
PH collapses further than \Delta^P_2. •
Mahaney's theorem (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. (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.
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. 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 \textbf{NP}\subseteq \textbf{P}/\text{poly}. == References ==