NC (复杂度)

✍ dations ◷ 2025-02-24 02:00:53 #数学中未解决的问题,复杂度类,计算机科学中未解决的问题

在计算复杂度理论,NC(Nick's Class),是一个复杂度类,是能被并行计算机在多对数函数时间((log ))内以多项式空间(或者说()并行线程)下解决的判定问题的集合,最先由史提芬·古克提出。

正如P被认为是易解复杂度类一般,NC也被认为是在并行计算上易解的问题。明显的有NC ⊆ P,因为一切并行计算都可以以多项式空间依次的在确定型图灵机上运行。我们目前仍未知道的一个关键问题是,NC = P是否成立。大多数的研究人员都认为这是不可能的——否则的话这意味着一切可计算函数都可以并行计算化。正如NP完全对于P来说是怀疑难解复杂度类一样,P完全对于NC来说也是“怀疑难解”的。

定义中的并行计算机,可以看作为一个并行,公共的PRAM池,所有的并行线程都可以在任意时间访问池的任意位置,NC的定义不受是否可以同时访问的影响,当然无论是CRCW,CREW还是EREW都是不受影响的。

RNC是随机化方向的对NC的扩展。

在计算复杂度理论,NC,是一个复杂度类,是能被并行计算机在(log )时间内以多项式空间下解决的判定问题的集合,那么明显地有以下性质:

此之为NC谱系。如果考虑和L,NL和AC的话那么有:

一个主要的而悬而未决的问题是,计算复杂度理论(的某些部分)对于NC谱系是否真的适用。Papadimitriou发现,如果设存在某些令

那么对于一切均存在

这一命题被称之为NC谱系崩塌,因为根据NC谱系链有

这意味着NC谱系有可能会崩塌到某个i值。对于这个问题,有两种可能性:

人们目前普遍认为(1)正确的,虽然还没有什么确切的证据。

相关

  • 理查·费曼理查德·菲利普斯·费曼, ForMemRS,英文名 Richard Philips Feynman ,(1918年5月11日-1988年2月15日),美国理论物理学家,以对量子力学的路径积分表述、量子电动力学、过冷液氦的超
  • 竞争性抑制作用酶(英语:Enzyme(/ˈɛnzaɪm/ )),是一类大分子生物催化剂。酶能加快化学反应的速度(即具有催化作用)。由酶催化的反应中,反应物称为底物,生成的物质称为产物。几乎所有细胞内的代谢过
  • 时间的B理论时间的B理论(英语:B-theory of time)是两个时间的理论立场中的其中一个立场的名称。相对于表示时间能在一条有序路线上运行之时间的A理论,B理论者论证时间的流动是错觉,过去、现
  • 毒物兴奋效应毒物兴奋效应(英语:Hormesis,源自希腊语hormáein,意为“激活”)是毒理学中用来描述毒物双相剂量效应的术语,与高剂量毒物对生物体有害;相反,低剂量毒物反而对生物体有益。其剂量效
  • 色散 (光学)在光学中,色散是指一道光中,光的相速度随着频率而改变。拥有上述特性的介质,我们称为色散性介质。提到色散,通常是指电磁波(包含可见光)的性质,但此性质可以推广至任何波动,例如声
  • 弗朗蒂谢克·拉伊托拉尔弗朗蒂谢克·拉伊托拉尔(捷克语:František Rajtoral,1986年3月12日-2017年4月23日)是捷克的一位足球运动员。在场上司职右后卫。效力于土耳其足球超级联赛的加济安泰普队(英语:Gaz
  • 施士元施士元(1908年3月18日-2007年9月27日)是一位中国核物理学家、教育家。江苏崇明(今上海崇明)人。他的父亲施禹传早年毕业于保定军官学校。曾就读于崇明三乐小学、上海浦东中学、北
  • 乔洁·黑尔乔洁·黑尔(又译乔洁特·黑尔,英语:Georgette Heyer,1902年8月16日-1974年7月)是一位英国历史罗曼史(英语:Historical_romance)与推理小说作家。写作生涯始于1921年时,将一个为弟弟而
  • 市村铁之助市村铁之助(1854年) - 明治6年(1873年)?)为美浓大垣藩出身的新选组队士。1854年(安政元年)出生、是大垣藩士市村半右卫门的第三个儿子 。1867年和哥哥辰之助一同加入新选组,成为土方
  • 马历·紫貂马历·紫貂(斯洛伐克语: ,1981年7月3日-)是一位斯洛伐克园林和景观设计师、专业的园丁、设计师和纹章艺术家。出生在捷克斯洛伐克的日利纳,是迪维纳当地人。他是斯洛伐克建筑师协