一元语言

✍ dations ◷ 2025-11-26 03:24:46 #一元语言

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

相关

骸骨骷髅或者髑髅、骸骨是已死的动物或人腐化或被吃剩的骨头，经常是死的象征，常被化身为死神或鬼的形像，也被当作材料，制成骨器。骨头常是坚硬的象征，也是人有气节的具体拟物化即“骨
弗朗索瓦·恩格勒弗朗索瓦·恩格勒（法语：François Englert，1932年11月6日－），比利时理论物理学家，在粒子物理学做出重要贡献。1964年，恩格勒和罗伯特·布绕特共同提出希格斯机制与希格斯玻色子理论。
mmol/L体积摩尔浓度（英语：molarity，通常以大寫M表示）是化学的一种通用浓度单位，体积摩尔浓度 c i
埃米尔·马勒埃米尔·马勒（法语：Émile Mâle，1862年－1954年），法国著名艺术史学家，法国中世纪图像志研究先驱，法兰西学术院院士。1862年，埃米尔·马勒生于法国阿列省的科芒特里（Commentry），父亲是一
本多真梨子本多真梨子（10月3日－），日本女性配音员。出身于神奈川县。A型血。原属Production Ace，现在是amuleto所属。毕业于日本工学院专门学校、AMUSEMENT MEDIA综合学院（日语：アミューズメン
列昂尼德·克拉夫丘克列昂尼德·马卡罗维奇·克拉夫丘克（乌克兰语：Леонід Макарович Кравчук，1934年1月10日－），乌克兰第一任总统，任期为1991年12月5日至1994年7月19日。（期间共任
WebDNAWebDNA是具有嵌入式数据库系统的解释型语言的Server-side scripting（英语：服务器端脚本），专门为万维网设计。它的主要用途是创建数据库驱动的动态网页应用程序。该名称于1995年
孔查可恩·宋善藤孔查可恩·宋善藤（泰语：กชกร ส่งแสงเติม，1992年8月21日－），出生地泰国曼谷，绰号 Gookgiik，是一名泰国女演员及模特。现为为泰国7台旗下艺人。Gookgiik于1992年8月21日
明朝礼部尚书明朝礼部尚书，为明朝六部中礼部的最高级长官，别称“大宗伯”（左右侍郎称“少宗伯”），负责掌管全国的礼仪、祭祀、宴飨、贡举、外交、宗教事务等政令，为正二品。永乐迁都后，明朝设置南京六部，其实“南京礼部尚书”以及其他五尚书等职位，多为虚衔，多为参赞机务或养清望闲职之所，重要性已无关政体本身。明朝洪武元年，朱元璋设置礼部。洪武六年，增设礼部尚书和礼部侍郎各一人，并在总部，祠部，膳部，主客部这四个部门各设郎中、员外郎各一人、主事各三人，隶属中书省。洪武十三年（1380年），因胡惟庸案，明太祖朱元璋罢黜宰相与中书省
土豆头蓝调土豆头蓝调（Potato Head Blues）是路易斯·阿姆斯特朗的一首音乐作品，被认为是他最好的唱片之一。1927年5月10日，路易斯·阿姆斯特朗和他的热门七人组（英语：Louis Armstrong and His Hot Seven）在美国伊利诺伊州芝加哥的奥克唱片（英语：Okeh Records）录制了这部唱片作品。