一元语言

✍ dations ◷ 2025-11-25 13:29:19 #一元语言

在计算复杂度理论内,一元语言或者结算语言是一种形式语言 (由字串组成的集合),里面所有的字串都是像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则将这个结果一般化到稀疏语言上面。

相关

  • 台北世界贸易中心坐标:25°2′2″N 121°33′44″E / 25.03389°N 121.56222°E / 25.03389; 121.56222台北世界贸易中心(简称台北世贸)位在台湾台北市信义计划区,为一座多功能的工商服务展演设
  • 不织布无纺布(non-woven fabric, non-woven cloth),又称不织布,是一种以针轧机械或梳理机械处理各种纤维原料,用高压形成或粘合生产的一种布状物。无纺布也分新旧技术或广义狭义。旧技
  • 火地省火地、南极和南大西洋诸岛省(西班牙语:Provincia de Tierra del Fuego, Antártida e Islas del Atlántico Sur)简称“火地省”,位于南美洲国家阿根廷南部,地处大火地岛东部,是该
  • 国民议会 (奥地利) 政治主题国民议会(德语:Nationalrat)是奥地利议会的下议院,根据宪法,国民议会和联邦议会(上议院)是平等的,但国民议会拥有更大权力,包括可以选举奥地利总理和组成联合政府,联合政府需
  • 万建民万建民(1960年6月-),江苏泰兴人。汉族。加入九三学社。南京农业大学作物遗传育种专业毕业。水稻分子遗传与育种专家。2015年12月当选中国工程院农业学部院士。1982年获南京农业
  • Jevons悖论在经济学中,当技术进步提高了使用资源的效率(减少任何一种使用所需的数量)时,Jevons悖论(有时是Jevons效应)就会发生,但资源消耗的速度上升是因为需求增加。 Jevons悖论也许是环境
  • 包提杰包提杰(英语:T.J. Burke,1993年3月3日-),台湾、美国混血,前男子职业篮球员,场上位置为大前锋。出生于台湾,幼时随父母移民美国。高中时期两度随校队闯进亚利桑那州准决赛,个人则一次获
  • FossilworksFossilworks(化石工厂)是一个古生物学在线数据库,由美国古生物学家、悉尼麦考瑞大学高级教职员约翰·阿尔罗伊(英语:John Alroy)(英文:John Alroy
  • 太元玉女太元玉女,亦称作“太元圣母”,是道教传说中的女仙,也是元始天王(即盘古)的配偶神,东王公和西王母的母亲。时常与玉清神母元君相互混同。有关她的记载主要见于葛洪所著的《元始上真众仙记·枕中书》。《元始上真众仙记·枕中书》记载:.mw-parser-output .templatequote{margin-top:0;overflow:hidden}.mw-parser-output .templatequote .templatequotecite{line-height:1em;text-align:lef
  • 李式 (三国)李式,凉州北地郡人(现在甘肃省东南部),汉末大司马、司隶校尉李傕之子,甚得李傕与妻子宠爱。李傕是东汉末年军阀;被曹操击败,李傕被夷三族。东晋袁宏《后汉纪·后汉孝献皇帝纪》:“汜、傕许和,质其爱子。…。傕之子式。…。傕妻爱式,和计未定。…。不以男,各女为质。”(《献帝起居注》、《后汉纪》)