稀疏语言

在计算复杂性理论里面, 稀疏语言是一种形式语言 (一堆字串的集合字串)，并且这语言内长度为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]