稀疏語言：修订间差异

删除的内容添加的内容

行内

2023年9月18日 (一) 16:36的最新版本

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

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

與其他語言的關係

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] EXPTIME ≠ NEXPTIME 若且唯若存在任何屬於NP的稀疏語言不屬於P。^[5] 在1999年，基於之前Ogihara的證明，Jin-Yi Cai和D. Sivakumar證明出若存在任何稀疏語言是P-完全 問題，則L = P.^[6]

參考資料

^ 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^{[永久失效連結]}
^ S. Fortune. A note on sparse complete sets. SIAM Journal on Computing, volume 8, issue 3, pp.431–433. 1979.
^ 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.
^ 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.
^ 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
^ 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 （页面存档备份，存于互联网档案馆）

外部連結

Lance Fortnow. Favorite Theorems: Small Sets. April 18, 2006. http://weblog.fortnow.com/2006/04/favorite-theorems-small-sets.html （页面存档备份，存于互联网档案馆）
Bill Gasarch. Sparse Sets (Tribute to Mahaney). June 29, 2007. http://weblog.fortnow.com/2007/06/sparse-sets-tribute-to-mahaney.html （页面存档备份，存于互联网档案馆）

Complexity Zoo: SPARSE

[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 （页面存档备份，存于互联网档案馆）

[1]

[2]

[3]

[4]

[5]

[6]

@@ 第1行： / 第1行： @@
+在[[計算複雜性理論]]裡面, '''稀疏語言'''是一種[[形式語言]] (一堆字串的集合[[字串]])，並且這語言內長度為''n''的字串個數，被一個''n''的[[多項式]]所限制住。 這種語言主要被用來研究'''[[NP (複雜度)|NP]]'''這類語言與其他種類語言的關係。包含所有稀疏語言的[[複雜度類]]被稱作'''SPARSE'''。
-{{Translating |time=2010-01-24T17:32:47+00:00 }}
-{{notchinese|1|24}}
+稀疏語言會被叫做''稀疏''的原因是因為，對任何語言，長度為''n''的字串可能性個數總共有2<sup>''n''</sup>個，而如果某特定語言只有包含這一些字串裡面的多項式個數個，那這語言所包含字串的比例會隨著''n''的成長很快的減少。 所有[[一元語言]]都是稀疏語言。一個稀疏語言比較不單純的例子是，某個語言包含所有恰有''k''個1(k是某個常數)的二進位字串，; 對任何長度''n'', 這個語言僅包含[[二項式係數|<math>\binom{n}{k}</math>]]個字串, 而這個數字則被 ''n''<sup>''k''</sup>給限制住。
-在[[計算複雜性理論]]裡面, '''稀疏語言'''是一種[[形式語言]] (a set of [[字串]])，並且這語言內長度為''n''的字串個數，被一個''n''的[[多項式]]限制住。 這種語言主要被用來研究'''[[NP (複雜度)|NP]]'''這類語言與其他種類語言的關係。包含所有稀疏語言的[[複雜度類]]被稱作'''SPARSE'''。
-稀疏語言會叫做''稀疏''的原因是因為，對任何語言，長度為''n''的字串總共有2<sup>''n''</sup>個，而如果某特定語言只有包含這一些字串裡面的多項式個數個，那這語言所包含字串的比例會隨著''n''的成長很快的減少。 所有[[一元語言]]s are sparse. An example of a nontrivial sparse language is the set of binary strings containing exactly ''k'' 1 bits for some fixed ''k''; for each ''n'', there are only [[Binomial coefficient|<math>\binom{n}{k}</math>]] strings in the language, which is bounded by ''n''<sup>''k''</sup>.
 == 與其他語言的關係 ==
-'''SPARSE'''包含了'''TALLY'''(包含所有[[一元語言]]的複雜度類)，因為'''TALLY'''裡面每一種長度的字串至多只有一個。雖然並非所有的'''[[P/poly]]'''語言都是稀疏語言，但對任何在'''P/poly'''裡面的語言均存在一個將之轉換為稀疏語言的[[多項式時間變換]]。<ref>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</ref> 在1979年，Fortune 證明若任何稀疏語言是[[co-NP-完全]]，則[[P/NP問題|P&nbsp;=&nbsp;NP]]；<ref>S. Fortune. A note on sparse complete sets. ''SIAM Journal on Computing'', volume 8, issue 3, pp.431&ndash;433. 1979.</ref> Mahaney在1982年利用這個證明了如果任何稀疏語言是[[NP-完全]], 則 P&nbsp;=&nbsp;NP (這就是[[Mahaney's theorem]]).<ref>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.</ref> A simpler proof of this based on left-sets was given by Ogihara and Osamu in 1991。<ref>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&ndash;483. 1991.</ref> '''[[EXPTIME]]''' &ne; '''[[NEXPTIME]]''' 若且唯若存在任何屬於NP的稀疏語言不屬於'''P'''。<ref>Juris Hartmanis, Neil Immerman, Vivian Sewelson. Sparse Sets in NP-P: EXPTIME versus NEXPTIME. ''Information and Control'', volume 65, issue 2/3, pp.158&ndash;181. 1985. [http://portal.acm.org/citation.cfm?id=808769 At ACM Digital Library]</ref> 在1999年，Jin-Yi Cai和D. Sivakumar, building on work by Ogihara, 證明若存在任何稀疏語言是'''[[P-完全]]''' 問題，則'''[[L (複雜度)|L]]''' = '''[[P (複雜度)|P]]'''.<ref>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&ndash;296. 1999. ISSN:0022-0000. [http://citeseer.ist.psu.edu/501645.html At Citeseer]</ref>
+'''SPARSE'''包含了'''TALLY'''(包含所有[[一元語言]]的複雜度類)，因為'''TALLY'''裡面每一種長度的字串至多只有一個。雖然並非所有的'''[[P/poly]]'''語言都是稀疏語言，但對任何在'''P/poly'''裡面的語言均存在一個將之轉換為稀疏語言的[[多項式時間變換]]。<ref>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{{dead link|date=2018年4月 |bot=InternetArchiveBot |fix-attempted=yes }}</ref> 在1979年，Fortune 證明若任何稀疏語言是[[co-NP-完全]]，則[[P/NP問題|P&nbsp;=&nbsp;NP]]；<ref>S. Fortune. A note on sparse complete sets. ''SIAM Journal on Computing'', volume 8, issue 3, pp.431–433. 1979.</ref> Mahaney在1982年利用這個證明了如果任何稀疏語言是[[NP-完全]], 則 P&nbsp;=&nbsp;NP (這就是[[Mahaney's theorem]]).<ref>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.</ref> 在1991年， Ogihara和Osamu提出一個基於left-sets的比較簡單的證明。<ref>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.</ref> '''[[EXPTIME]]''' ≠ '''[[NEXPTIME]]''' 若且唯若存在任何屬於NP的稀疏語言不屬於'''P'''。<ref>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. [http://portal.acm.org/citation.cfm?id=808769 At ACM Digital Library] {{Webarchive|url=https://archive.today/20120712205722/http://portal.acm.org/citation.cfm?id=808769 |date=2012-07-12 }}</ref> 在1999年，基於之前Ogihara的證明，Jin-Yi Cai和D. Sivakumar證明出若存在任何稀疏語言是'''[[P-完全]]''' 問題，則'''[[L (複雜度)|L]]''' = '''[[P (複雜度)|P]]'''.<ref>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. [http://citeseer.ist.psu.edu/501645.html At Citeseer] {{Wayback|url=http://citeseer.ist.psu.edu/501645.html |date=20071109091944 }}</ref>
 == 參考資料 ==
 <references />
-== 外部連接 ==
+== 外部連結 ==
-* Lance Fortnow. Favorite Theorems: Small Sets. April 18, 2006. http://weblog.fortnow.com/2006/04/favorite-theorems-small-sets.html
+* Lance Fortnow. Favorite Theorems: Small Sets. April 18, 2006. http://weblog.fortnow.com/2006/04/favorite-theorems-small-sets.html {{Wayback|url=http://weblog.fortnow.com/2006/04/favorite-theorems-small-sets.html |date=20090220180359 }}
-* Bill Gasarch. Sparse Sets (Tribute to Mahaney). June 29, 2007. http://weblog.fortnow.com/2007/06/sparse-sets-tribute-to-mahaney.html
+* Bill Gasarch. Sparse Sets (Tribute to Mahaney). June 29, 2007. http://weblog.fortnow.com/2007/06/sparse-sets-tribute-to-mahaney.html {{Wayback|url=http://weblog.fortnow.com/2007/06/sparse-sets-tribute-to-mahaney.html |date=20090424085339 }}
 * {{CZoo|SPARSE|S#sparse}}
@@ 第21行： / 第18行： @@
 [[Category:形式語言]]
 [[Category:計算複雜性理論]]
-[[en:sparse language]]