NC (复杂度)

✍ dations ◷ 2025-06-28 18:25:14 #数学中未解决的问题,复杂度类,计算机科学中未解决的问题

在计算复杂度理论,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)正确的,虽然还没有什么确切的证据。

相关

  • 梅斯卡尔酒梅斯卡尔酒(Mezcal)是龙舌兰酒的一种,主要产于墨西哥南部的瓦哈卡州,根据墨西哥1994年通过的新法律,只有6个行政区生产的龙舌兰酒可以称为梅斯卡尔酒,原料也只限在特定的五种龙舌
  • 杀生杀生是指杀害生命,一般指杀死动物。杀生一词最早见诸《汉书·公孙弘传》,此中“杀生”是指“杀之或使之生”,而非杀害生命。在佛教中,对屠宰和屠宰业者持谴责态度,列为十恶之首。
  • 广东药科大学广东药科大学是广东省属普通高等院校,全国独立建制的四所药科类高等院校之一,广东省培养药学、预防医学和临床医学等高级技术人才和管理干部的重要基地,是国家大学生文化素质教
  • 金融风险金融风险,指任何有可能导致企业或机构财务损失的风险。
  • 谢拉谢拉县(Sierra County, California)是美国加利福尼亚州东部内华达山脉的一个县,东邻内华达州。面积2,491平方公里,根据美国2000年人口普查数字,共有人口3,555人。县治唐尼维尔 (D
  • 起锚起锚可以指:
  • 美鞭达唑甲苯咪唑(英语:Mebendazole,简称MBZ),又名安乐士、美鞭达唑,为治疗多种寄生虫感染的指定用药。治疗对象包含蛔虫、蛲虫、线虫、绦虫、钩虫、滴虫、包囊虫,以及鞭虫类的感染。该药属
  • 藤球藤球(印尼语 : "sepak takraw"; 马来语 :"sepak raga"; 爪夷文: سيڤق تكراو or سيڤق راڬا; 泰语:ตะกร้อ, 皇家音译:takro, 发音:; 高棉语:"សីដក់
  • 若昂·阿维兰热让-玛丽·福斯坦·戈德弗鲁瓦·德·阿维兰热(葡萄牙语:Jean-Marie Faustin Goedefroid de Havelange,通常称作若昂·阿维兰热(葡萄牙语:João Havelange)博士,1916年5月8日-2016年8
  • 赫子铭郝子铭(1982年8月4日-),生于中国黑龙江省鹤岗市,中国大陆男艺人,其前妻是著名选秀歌手何洁,育有一子一女。2005年 重庆卫视《天生一对》主持人