NL完全

✍ dations ◷ 2025-11-20 12:15:13 #计算复杂性理论,理论计算机科学

在计算复杂性理论中,NL完全是由全体对NL类完备的语言构成的复杂性类。也就是说,NL完全的语言是NL类中最“难解”和最“有力”的语言。如果有某个确定性的方法可以在对数空间内解决一个NL完全问题,那么就会有NL=L。

在全体判定问题中,NL类包含了那些可以用非确定型图灵机在对数空间内解决的问题。这里的图灵机要求有一条只读输入带,和另一条空间上限与输入长度的对数成比例的读写带。类似地,L类包含了可以用同样结构的确定型图灵机解决的判定问题。由于这种图灵机的格局数目只有多项式级别,因此NL和L都是P的子集。

正式地说,一个问题是NL完全的,当且仅当它属于NL,并且所有NL中的判定问题都可以Log-空间规约到它。

相关

  • β-硝基丙酸β-硝基丙酸(3-硝基丙酸,BPA,3-NPA,C3H5NO4)是一种真菌毒素,其对线粒体有抑制作用对人体有毒。许多真菌产生这种毒素,因此广泛存在于食品如甘蔗,以及通过真菌发酵的日本主食味噌,酱油
  • 淡水镇淡水区,旧称沪尾 (闽南语:Hóo-bué/Hōo-bé),位于中华民国新北市西北沿海以及淡水河的出海口北侧,北邻三芝区,南邻台北市北投区,西滨台湾海峡,西南与八里区间以淡水河为界。而在
  • 威尔弗里德·劳雷尔威尔弗里德·劳雷尔爵士(Sir Wilfrid Laurier,1841年11月20日-1919年2月17日)是第七任,也是首位法裔加拿大总理。任内曾经历第二次布尔战争。其肖像现在印于加拿大五元钞票上。安
  • 海兔见内文海鹿属(学名:Aplysia),又名海兔属,是分类上的一个属,为海洋腹足纲软体动物。海鹿属物种的体型尺寸变化大,当中非常大的种类特称为海兔,有关这些海兔们共通性的描述可以在海兔
  • 铜族固体、 液体、 气体11族元素(常称铜族元素)是指元素周期表上第11族(ⅠB族)的元素,位于10族元素和12族元素之间。11族元素包含铜(Cu)、银(Ag)、金(Au)、
  • 王士祯清禹之鼎绘《王士禛幽篁坐啸图卷》,故宫博物院藏王士禛(1634年9月17日-1711年6月26日),赐名士祯,小名豫孙,字贻上,号阮亭,别号渔洋山人,人称王渔洋,谥文简。山东新城(今山东桓台)人,清代著
  • 莲花街道莲花街道是中国广东省深圳市福田区下辖的一个街道。总面积9.6平方公里,下辖12个社区。总人口约22万人,其中户籍人口约10万人。是深圳市人大常委会、深圳市政府的驻地,是深圳市
  • 日耳曼尼亚志《日耳曼尼亚志》(拉丁语:,意为“关于日耳曼人的起源和分布”),罗马历史学家塔西佗著,于公元98年完成。记述了公元1世纪左右的日耳曼部族的分布情况。篇幅不长,但有极高的史学价值
  • 雅纳尔·塔茨雅纳尔·塔茨(爱沙尼亚语:Janar Talts,1983年4月7日-),爱沙尼亚篮球运动员,现在效力于意大利球队瓦雷泽篮球俱乐部。他也代表爱沙尼亚国家男子篮球队参赛。
  • 威化威化(英语:wafer),又称为维夫,是一种夹心饼干,有时会伴随雪糕一同食用。威化通常为长条形状,表面满布细小方格,中间有两至三层的甜味馅料(如果酱、巧克力、花生酱等)。