NL完全

✍ dations ◷ 2025-11-24 09:10:58 #计算复杂性理论,理论计算机科学

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

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

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

相关

  • 链束植物门真蕨纲(Polypodiopsida),又称为链束植物(Monilophytes)是植物界中真叶植物下的两个演化支之一,是种子植物的姊妹群。真蕨纲比起较原始的石松门多了真正的叶子,但比起较进化的种子植
  • 睡眠瘫痪症睡眠瘫痪症(英:Sleep Paralysis)又称睡瘫,梦魇,睡眠麻痹,在民间也把此类症状叫作鬼压身、鬼压床。此类症状被医学认为是一种疾病。睡眠瘫痪症通常发生在人类刚进入睡眠或将醒未醒
  • A Song for ××《A Song for xx》(给xx之歌)是日本歌手滨崎步的第一张专辑,1999年1月1日于日本发售。滨崎步在这张专辑发行前,单曲销售的成绩并没有特别的亮眼。但这张专辑却出乎意料的首周占
  • 真穴鸟类真穴鸟类(学名:Eucavitaves)这一演化支包括咬鹃目(学名:Trogoniformes)和䴕翠鸟类(学名:Picocoraciae,包括:啄木鸟、翠鸟、犀鸟和戴胜这一大群鸟),因为这些鸟种大多在洞穴筑巢。鹃
  • 行政权力行政机关(常任文官)具有政策影响力的原因:立法机关在法律上虽仍有立法权,但是从实质立法过程观察,一般都已失去真正立法(制定政策)的能力,而转为承担批评、监督、象征等角色。其原
  • 白粉菌目见内文白粉菌目(学名:Erysiphales)是子囊菌门锤舌菌纲的一目,该目仅有白粉菌科(Erysiphaceae)一单科。本目真菌通常寄生在植物表面,其产生的大量分生孢子梗与分生孢子使植物表面看
  • 原劳亚大陆原劳亚大陆(Proto-Gondwana)意为“最初的劳亚大陆”,是个史前大陆。原劳亚大陆曾先后是罗迪尼亚大陆、潘诺西亚大陆的一部分。在罗迪尼亚大陆时期,后来的劳伦大陆东侧连接者华南
  • 胡姆斯胡姆斯 (英语: 或 ; 错误:{{lang-xx}}:文本有斜体标记(帮助))是利比亚西北部的一座沿地中海城市,位于的黎波里和米苏拉塔之间,2009年大约有202,000人。
  • 阿丽尔·李阿丽尔·李(英语:Ariel Lee,1999年5月15日-),美国女子羽毛球运动员。2017年9月,阿丽尔·李出战墨西哥羽毛球国际赛,与西德尼·李合作拿得女子双打比赛亚军。只列出曾进入半决赛的国
  • 露丝·哈迪卡露丝·哈迪卡(捷克语:Lucie Hradecká,1985年5月21日-)是捷克职业网球女运动员,2004年转职业。她的WTA生涯最高单打排名为第28(2012年2月27日)。