基本介紹
- 中文名：稀疏語言
- 外文名：Sparse language
- 本質：一種形式語言
- 學科：計算機科學
概述,解釋,與其他語言的關係,
概述
這種語言主要被用來研究NP這類語言與其他種類語言的關係。
包含所有稀疏語言的複雜度類被稱作SPARSE。
解釋
稀疏語言會被叫做稀疏的原因是因為，對任何語言，長度為n的字串可能性個數總共有2n個，而如果某特定語言只有包含這一些字串裡面的多項式個數個，那這語言所包含字串的比例會隨著n的成長很快的減少。
所有一元語言都是稀疏語言。
一個稀疏語言比較不單純的例子是，某個語言包含所有恰有k個1(k是某個常數)的二進制字串，對任何長度n，這個語言僅包含
個字串, 而這個數字則被nk給限制住。
與其他語言的關係
SPARSE包含了TALLY(包含所有一元語言的複雜度類)，因為TALLY裡面每一種長度的字串至多只有一個。雖然並非所有的P/poly語言都是稀疏語言，但對任何在P/poly裡面的語言均存在一個將之轉換為稀疏語言的多項式時間變換。
在1979年，Fortune 證明若任何稀疏語言是co-NP-完全，則P=NP；Mahaney在1982年利用這個證明了如果任何稀疏語言是NP-完全, 則 P=NP (這就是Mahaney's theorem)。
在1991年， Ogihara和Osamu提出一個基於left-sets的比較簡單的證明。EXPTIME≠NEXPTIME若且唯若存在任何屬於NP的稀疏語言不屬於P。
