单数语言

在计算复杂性理论中，单数语言或理数语言是一种形式语言（一组字符串），其中所有的字符串都有1k的形式，其中1可以是任何固定符号。例如，语言{1,111,1111}是单数，语言{1k|k是素数}也是如此。所有这类语言的复杂性类别有时被称为TALLY。单项语言的名称来自于这样一个事实：单项语言是对一组自然数在单项数字系统中的编码。由于任何有限字母表上的字符串宇宙是一个可数集，每一种语言都可以被映射到一个xxx的自然数集A；因此，每一种语言都有一个单数版本{1k|kinA}。反过来说，每一种单数语言都有一个更紧凑的二进制版本，即自然数k的二进制编码的集合，这样1k就在语言中。由于复杂性通常以输入字符串的长度来衡量，一种语言的单数版本可能比原始语言更容易。例如，如果一种语言可以在O(2n)时间内被识别，那么它的单字母版本可以在O(n)时间内被识别，因为n已经变得指数级大。

更一般地说，如果一种语言可以在O(f(n))时间和O(g(n))空间内被识别，那么它的单字母版本可以在O(n+f(logn))时间和O(g(logn))空间内被识别（我们仅仅需要O(n)时间来读取输入字符串）。然而，如果一种语言的成员资格是不可判定的，那么其单数版本的成员资格也是不可判定的。

TALLY包含在P/poly中--在给定一个只取决于输入长度的建议函数后，可以在多项式时间内识别的语言类别。在这种情况下，所需的建议函数非常简单--它为每个输入长度k返回一个比特，指定1k是否在该语言中。一个单数语言必然是稀疏语言，因为对于每个n，它最多包含一个长度为n的值和最多n个长度为n的值，但并非所有的稀疏语言都是单数；因此TALLY包含在SPARSE中。人们认为不存在NP难的单数语言：如果存在一个NP不完全的单数语言，那么P=NP。这个结果可以扩展到稀疏语言。如果L是一种单数语言，那么L*（L的Kleene星）就是一种规则语言。

复杂度类P1是能被多项式时间图灵机识别的单数语言类（给定其输入为单数）；它是P类的类似物。一个计数类#P1，即#P的类似物，也是已知的。