一元语言

在计算复杂度理论内，一元语言或者结算语言是一种形式语言 (由字串组成的集合)，里面所有的字串都是像1^k的形式(这里的"1"可以是任何的符号）。例如，{1, 111, 1111}就是一个一元语言,或是像{1^k | k是质数}。这一类语言的复杂度类有时被叫做TALLY。

理论[编辑]

"一元"这个名字的起源来自于我们可以将一元语言视为将语言转成自然数后，再以一进位系统转出来产生的语言。既然所有语言的字串均可以视作有限字母的集合，故字串的集合必然属于可数集。所以我们可以将任何语言内所有字串一一对应到一个自然数的集合A; 因此之故，我们可以知道，任何语言均有它的一元版本{1^k | k 属于A}。相对应的，任何一元语言也可以变成它比较小型的二进制版本，只要我们将这一元语言的字串1^k对应到k的二进制表示法即可。

因为复杂度常常以输入的字串长度来作基准，所以一个语言的"一元版本"常常会比较简单。举例来说，如果一个语言要花O(2ⁿ)的时间来解读，它的一元版本则需要O(n) 的时间，因为把语言的每个符号都换成"1"会让这个语言的空间呈现对数比例的缩减。更广义来说，如果一个语言可以用O(f(n))的时间以及O(g(n)) 的空间解读，那他的一元版本解读起来则需要O(n + f(log n))的时间和O(g(log n))的空间 (多加的O(n)时间是因为我们起码需要这些时间来读取输入字串)。不过，如果一个语言是不可决定的, 那这个语言的一元版本也是不可决定的(没有变得比较简单)。

与其他复杂度类的关系[编辑]

TALLY包含在P/poly（英语：P/poly）内，因为我们可以对每一个k用一个一位元的建议字串来分辨1^k 是否在这个语言中。任何一元语言都必然是属于稀疏语言, 因为对任何自然数n，一元语言对长度为n的字串至多只有一个，所以对长度至多为n的字串也只有n个(合乎稀疏语言的定义)，但是并非所有的稀疏语言都是一元语言；因此TALLY包含在SPARSE里面。 Piotr Berman 在1978年证明了若任何一元语言是NP-完全，则P = NP,^[1] Mahaney则将这个结果一般化到稀疏语言上面。^[2]

参考资料[编辑]

注释[编辑]

^ Piotr Berman. Relationship between density and deterministic complexity of NP-complete languages. In Proceedings of the 5th Conference on Automata, Languages and Programming, pp.63–71. Springer-Verlag. Lecture Notes in Computer Science #62. 1978.
^ 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.

一般参考[编辑]

Lance Fortnow. Favorite Theorems: Small Sets. April 18, 2006. Computational Complexity: Favorite Theorems: Small Sets （页面存档备份，存于互联网档案馆）
Scott Aaronson（英语：Scott Aaronson）: Complexity Zoo:T - Qwiki

[1] Piotr Berman. Relationship between density and deterministic complexity of NP-complete languages. In Proceedings of the 5th Conference on Automata, Languages and Programming, pp.63–71. Springer-Verlag. Lecture Notes in Computer Science #62. 1978.

[2] 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.

[1]

[2]