一元语言

✍ dations ◷ 2025-05-11 02:10:05 #一元语言

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

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

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

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

相关

  • 理型理型论(英语:theory of Forms,或theory of Ideas),西方哲学对于本体论与知识论的一种观点,由柏拉图提出。理型论认为,在人类感官能够感受到事物的共相之上,存在着一种抽象的完美理型
  • 批判法律研究批判法律研究(Critical legal studies),又译为批判法学派 ,是20世纪70年代兴起的一支激进的法学流派。批判法律研究的思想起源可以追溯到美国法律现实主义,而作为一支独立的学术
  • 波多黎各自由邦面积以下资讯是以2015年估计国家领袖国内生产总值(购买力平价) 以下资讯是以2016年估计国内生产总值(国际汇率)人类发展指数 以下资讯是以2014估计波多黎各自由邦(英语:The Common
  • ATC代码 (J02)A·B·C·D·G·H·QI·J·L·M·N·P·R·S·VATC代码J02(抗真菌药)是解剖学治疗学及化学分类系统的一个药物分组,这是由世界卫生组织药物统计方法整合中心(The WHO Collaborat
  • 1981年南斯拉夫人口普查1981年南斯拉夫人口普查是南斯拉夫自1921年来的第7次人口普查,也是第二次世界大战以后的第5次人口普查。普查标准日在1981年3月31日。南斯拉夫的下一次人口普查在1991年3月底
  • 刘树梅刘树梅(1891年1月14日-1940年2月16日)。别名刘锡章,祖籍湖南省阮陵县。早年参加辛亥革命,1912年公费赴美国学习财经专业,1920年毕业于美国哈佛大学。回国后在上海执教,1924年出版《
  • 强自修强自修(1903年-1988年9月),字琢为,化名强枉笙,男,陕西宜君人,中华人民共和国政治人物,曾任甘肃省人大常委会副主任,中国人民政治协商会议第一届全体会议代表。
  • 考德威尔·埃塞尔斯廷考德威尔·埃塞尔斯廷(英语:Caldwell Esselstyn,1933年12月12日-),美国男子赛艇运动员。他曾代表美国参加1956年夏季奥林匹克运动会赛艇比赛,获得男子八人单桨有舵手金牌。
  • 回扣回扣或回佣、退佣是指供应商按一定比例,将货款返还给销售商的资金。根据行业和地区的不同,回扣可能违法,也可能不违法,视乎交易各方是否均知悉及容许。回扣在商业领域是一种普遍现象。据称戴尔每年可以从英特尔手中,获得十亿美元的回扣。
  • 格奥尔基·沃罗诺伊格奥尔基·费奥多谢维奇·沃罗诺伊(乌克兰语:Георгій Феодосійович Вороний;俄语:Гео́ргий Феодо́сьевич Вороно́й;1868年4月28日-1908年11月20日),乌克兰及俄国数学家。沃罗诺伊最知名的贡献是建立了沃罗诺伊图。沃罗诺伊生于俄罗斯帝国波尔塔瓦省(今乌克兰切尔尼戈夫州)。1889年,进入圣彼得堡大学学习。1894年,成为华沙大学教授。1908年,因病逝世于家乡。