几率图灵机

✍ dations ◷ 2025-04-02 16:51:35 #计算机科学中未解决的问题,计算模型,概率复杂度理论,图灵机

在计算复杂性理论内,几率图灵机是一个非决定型图灵机,在每个转折点根据某种概率分布随机选择某种可行的转变(transition)。

在转变是均匀分布几率的例子里面,我们可以定义为决定型图灵机多了一个新增的"写入"指令,这一个写入指令的值是所有图灵机能用符号的均匀分布几率选择出的符号 (概括地说,这个写入指令以相同的几率在纸带上面写入'1'或者'0'。) 另一个常用的定义是多了一条,上面布满了许多随机位元值的确定型图灵机。

所以,几率图灵机可以有随机的结果(与决定型图灵机不同);给定一个输入和一个状态机,机器运作的时间长度会不同,或者甚至不会停止; 甚至,这机器可能在这一次操作下回传为接受,下一次相同的输入值却回传为拒绝。

因此如何去理解被一个几率图灵机接受字串的方式可以用许多不同的方式定义。 同时也有许多种因为我们对accept方式的不同,而产生了许多的多项式时间随机复杂度类,包含了 RP,Co-RP,BPP and ZPP。 如果我们把多项式时间的限制改成对数空间的限制,我们则有了跟上面雷同的RL,Co-RL,BPL,和ZPL。如果我们同时限制两者,则有了RLP,Co-RLP,BPLP,和ZPLP。

随机计算对于定义大多数的交互式证明系统也是极为重要的,因为验证者机器需要随机性来避免被全能的证明者预测或者欺骗。 例如说,IP这个类别等同 PSPACE,但是如果把验证者的随机性移除,我们就只有NP,一个一般而言相信(但尚未证明)是比起IP要小的复杂度类。

复杂度理论的其中一个重点问题是:是否随机性增加了算法的能力? 换句话说,是否有问题在多项式时间内可以以概率图灵机解决但是不能以决定型图灵机解决?或者是决定型图灵机可以在至多只有多项式时间的变慢之下,完全的模仿随机图灵机的动作?现今的研究者大部分相信后者,这同时可以推出 P = BPP。相同问题的对数空间(log space)版本(是否L = BPLP?)则比起多项式时间版本更被广泛相信为真。另外,随机性给予交互式证明系统的力量,以及对困难问题所能建立更简单的算法的特质,例如多项式时间内的质数测试(primality testing)和对数空间的图相连测试(graph connectedness testing),又隐含着随机性是有可能增加计算能力的。

量子计算机则是另一种先天就具有着几率性质的计算模式。

相关

  • 假性怀孕假性怀孕是一种临床或是亚临床的症状,指生物在临床上出现一些怀孕的迹象(例如闭经、孕吐、乳房胀痛,甚至是腹胀,但事实上并非真正怀孕。临床上,人类以外的动物常出现假性怀孕(特别
  • α衰变α衰变(Alpha decay,又称alpha衰变)是一种放射性衰变(核衰变);发生α衰变时,一颗α粒子会从原子核中射出(附注:α粒子,又名阿尔法粒子,即氦-4核,42He ,即一颗由2颗质子和2颗中子组成的原
  • MicrobotryomycetesHeterogastridiales 白冬孢酵母目(Leucosporidiales) 微球黑粉菌目(Microbotryales) 锁掷酵母目(Sporidiobolales)微球黑粉菌纲(学名:Microbotryomycetes)是担子菌门柄锈菌亚门下的一
  • 增塑剂塑化剂(英语:Plasticizer),或称增塑剂、可塑剂,是一种增加材料的柔软性或使材料液化的添加剂。其添加对象包含了塑胶(塑胶添加剂)、混凝土、干壁材料、水泥、胶粘剂与石膏等等。同
  • 白垩刺甲鲨白垩刺甲鲨(学名:Cretoxyrhina)是生存于白垩纪的一属大型鲨鱼。白垩刺甲鲨是由路易士·阿格西(Louis Agassiz)于1843年命名。后来查尔斯·斯腾伯格(Charles H. Sternberg)于1890年
  • 黛芬·赛赫意黛芬·赛赫意(法语:Delphine Seyrig,1932年4月10日-1990年10月15日)是法国演员。1963年,她因演出《穆里爱》而于第24届威尼斯影展获得最佳女演员。
  • 约翰·库利奇·亚当斯约翰·库利奇·亚当斯(英语:John Coolidge Adams,1947年2月15日-),一般简称为约翰·亚当斯或亚当斯,美国当代古典音乐作曲家,简约主义音乐的代表人物之一。亚当斯的音乐结合了简约主
  • 登巴德尼亚王朝檀巴德尼耶王朝成立于1255年,为斯里兰卡(锡兰)中世纪的独立王朝,该王朝首都为锡兰北方城市檀巴德尼耶,亦是王朝名称缘由。檀巴德尼耶王朝崛起于1215年,于战胜趋走马来人后,统治了锡
  • 中国2010年上海世界博览会民营企业联合馆中国2010年上海世界博览会民营企业联合馆,简称民营企业联合馆、中国民企联合馆(英文:Chinese Private Enterprise at Expo 2010),是中国2010年上海世界博览会的中国民营企业联合
  • 布鲁斯·斯普林斯汀布鲁斯·斯普林斯汀(英语:Bruce Frederick Joseph Springsteen,1949年9月23日-),昵称 "The Boss",美国摇滚歌手、歌曲创作者与吉他手。斯普林斯汀经常与E街乐团共同创作与巡回演出,