跳至內容

稀疏語言

維基百科,自由的百科全書

計算複雜性理論裡面, 稀疏語言是一種形式語言 (一堆字串的集合字串),並且這語言內長度為n的字串個數,被一個n多項式所限制住。 這種語言主要被用來研究NP這類語言與其他種類語言的關係。包含所有稀疏語言的複雜度類被稱作SPARSE

稀疏語言會被叫做稀疏的原因是因為,對任何語言,長度為n的字串可能性個數總共有2n個,而如果某特定語言只有包含這一些字串裡面的多項式個數個,那這語言所包含字串的比例會隨著n的成長很快的減少。 所有一元語言都是稀疏語言。一個稀疏語言比較不單純的例子是,某個語言包含所有恰有k個1(k是某個常數)的二進位字串,; 對任何長度n, 這個語言僅包含個字串, 而這個數字則被 nk給限制住。

與其他語言的關係

SPARSE包含了TALLY(包含所有一元語言的複雜度類),因為TALLY裡面每一種長度的字串至多只有一個。雖然並非所有的P/poly語言都是稀疏語言,但對任何在P/poly裡面的語言均存在一個將之轉換為稀疏語言的多項式時間變換[1] 在1979年,Fortune 證明若任何稀疏語言是co-NP-完全,則P = NP[2] Mahaney在1982年利用這個證明了如果任何稀疏語言是NP-完全, 則 P = NP (這就是Mahaney's theorem).[3] 在1991年, Ogihara和Osamu提出一個基於left-sets的比較簡單的證明。[4] EXPTIMENEXPTIME 若且唯若存在任何屬於NP的稀疏語言不屬於P[5] 在1999年,基於之前Ogihara的證明,Jin-Yi Cai和D. Sivakumar證明出若存在任何稀疏語言是P-完全 問題,則L = P.[6]

參考資料

  1. ^ Jin-Yi Cai. Lecture 11: P=poly, Sparse Sets, and Mahaney's Theorem. CS 810: Introduction to Complexity Theory. The University of Wisconsin–Madison. September 18, 2003. http://pages.cs.wisc.edu/~jyc/810notes/lecture11.pdf[永久失效連結]
  2. ^ S. Fortune. A note on sparse complete sets. SIAM Journal on Computing, volume 8, issue 3, pp.431–433. 1979.
  3. ^ S. R. Mahaney. Sparse complete sets for NP: Solution of a conjecture by Berman and Hartmanis. Journal of Computer and System Sciences 25:130-143. 1982.
  4. ^ M. Ogiwara and O. Watanabe. On polynomial time bounded truth-table reducibility of NP sets to sparse sets. SIAM Journal on Computing volume 20, pp.471–483. 1991.
  5. ^ Juris Hartmanis, Neil Immerman, Vivian Sewelson. Sparse Sets in NP-P: EXPTIME versus NEXPTIME. Information and Control, volume 65, issue 2/3, pp.158–181. 1985. At ACM Digital Library Archive.is存檔,存檔日期2012-07-12
  6. ^ Jin-Yi Cai and D. Sivakumar. Sparse hard sets for P: resolution of a conjecture of Hartmanis. Journal of Computer and System Sciences, volume 58, issue 2, pp.280–296. 1999. ISSN:0022-0000. At Citeseer頁面存檔備份,存於網際網路檔案館

外部連結