在計算復雜性理論中，稀疏語言是一種形式語言（一組字符串），其復雜性函數，計算語言中長度為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。