一元语言

✍ dations ◷ 2025-11-26 16:30:33 #一元语言

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

相关

  • 经皮主动脉瓣置换术在经皮主动脉瓣置换术或经导管主动脉瓣植入术(TAVI)中,置换的瓣膜经腹股沟处的股动脉导管,向上达到升主动脉。这一技术取代了更具创伤性的开胸手术。两者的术后生存率相持平,但是
  • 塞伦盖蒂国家公园塞伦盖蒂国家公园是坦桑尼亚的一座大型国家公园,位于塞伦盖蒂地区,因每年都会出现超过150万只牛羚和约25万只斑马的大规模迁徙而闻名。1981年列入组织世界遗产名录。马赛人多
  • 狡大丝油鲶狡大丝油鲶,为辐鳍鱼纲鲶形目长须鲶科的其中一种,分布于南美洲巴拉那河流域,体长可达40公分,属肉食性,生活习性不明。 维基物种中有关狡大丝油鲶的数据
  • 马克·布鲁姆马克·布鲁姆(英语:Mark Blum,1950年5月14日-2020年3月25日),美国演员,曾获得奥比奖(英语:Obie Award)。布鲁姆出生在新泽西州纽华克。1968年毕业于该州的哥伦比亚高级中学(英语:Columbi
  • 他纳·科曼他纳·科曼(泰语:ถนัด คอมันตร์;皇家音译:,1914年5月9日-2016年3月3日),泰国外交官、政治家,曾于1959年至1971年期间担任泰国外交部部长,于1979年至1982年期间担任民主党
  • 卡尔·瓦内特纳粹集中营转移营比利时:布伦东克堡垒 · 梅赫伦转移营法国:居尔集中营 · 德朗西集中营意大利:波尔查诺转移营荷兰:阿默斯福特集中营 · 韦斯特博克转移营挪威:法斯塔德集中营部
  • 角动量图出现在量子力学以及其应用如多体问题、量子化学等领域中,角动量图是一种图形表示法,用以代表一量子系统的角动量量子态,使得相关计算能以符号形式推演。此方法的箭号将角动量态
  • 石生龙石生龙(1955年10月-),辽宁庄河人。1976年加入中国共产党。北京航空学院(现北京航空航天大学)材料科学与工程系金属材料专业毕业,研究生学历,工学硕士。历任监察部副处长、处长,中纪委第一纪检监察室处长、副主任、主任,第四纪检监察室主任,中央纪委驻最高人民检察院纪检组组长等职。2008年调任广西壮族自治区党委常委、纪委书记。2014年1月,调任中纪委驻住建部纪检组组长。
  • 崔英俊崔英俊(韩语:최영준,1980年7月7日-),韩国男演员。歌手出身,与全相焕、李正、徐在浩以7Dayz出道,并为团体中的队长。组合解散后,崔英俊就入伍了,退伍后通过音乐剧试镜成为演员。
  • 二碲化锝二碲化锝是一种无机化合物,化学式为TcTe2。它可由碲和锝在高温反应得到。它是一种半导体,根据HSE06计算,块材的1Tdp相的间接带隙为0.37 eV,单层材料增大至1.21 eV。除了TcTe2外,另一已知的碲化物是Tc6Te15,碲和锝按10:1反应得到。