稀疏语言

在计算复杂性理论中，稀疏语言是一种形式语言（一组字符串），其复杂性函数，计算语言中长度为n的字符串的数量，被n的多项式函数所约束。它们主要用于研究复杂性类NP与其他类的关系。所有稀疏语言的复杂性类被称为SPARSE。稀疏语言之所以被称为稀疏，是因为总共有2n个长度为n的字符串，如果一种语言只包含多项式的这些字符串，那么随着n的增长，它所包含的长度为n的字符串的比例迅速归零。

所有的单数语言都是稀疏的。一个非简单的稀疏语言的例子是二进制字符串的集合，在某个固定的k下正好包含k1比特；对于每个n，只有{displaystyle{binom{n}{k}}}语言中的字符串。语言中的字符串，它以nk为界。

与其他复杂度类别的关系SPARSE包含TALLY，即单数语言的类别，因为这些语言最多只有一个任何长度的字符串。虽然不是所有P/poly中的语言都是稀疏的，但从P/poly中的任何语言到稀疏语言都有一个多项式时间的图灵还原。

Fortune在1979年表明，如果任何稀疏语言是共NP完备的，那么P=NP；Mahaney利用这一点在1982年表明，如果任何稀疏语言是NP完备的，那么P=NP（这就是Mahaney的定理）。

Ogihara和Watanabe在1991年给出一个基于左集的更简单证明。Mahaney的论证实际上并不要求稀疏语言在NP中（因为NP硬稀疏集的存在意味着NP完整稀疏集的存在），所以当且仅当P=NP时，存在一个NP硬稀疏集。

此外，当且仅当NP中存在不在P中的稀疏语言，E≠NE。1999年，Jin-YiCai和D.Sivakumar在Ogihara的工作基础上表明，如果存在一个稀疏的P-完全问题，那么L=P。