L (复杂度)

✍ dations ◷ 2025-04-02 08:39:00 #数学中未解决的问题,复杂度类,概率复杂度类,闭包算子,计算机科学中未解决的问题

L也称为LSPACE或DLOGSPACE,是计算复杂度理论中能被确定型图灵机利用对数空间解决的判定问题集合。

对数空间是指与输入规模成对数大小关系的可写的储存空间,大多数对数空间(LOGSPACE)算法以这种方式储存。

重要的相关未解问题包括复杂度类L和P是否恒等(L = P)及复杂度类L和NL是否恒等(L = NL)。目前已知有以下重要性质:

和功能性问题相关的类别是FL,在计算复杂度理论,FL是一个复杂度类,是能被确定型图灵机在对数空间下解决的函数问题的集合。

依照同样的原理,可以定义相应的FP,FNP,TFNP。

FL常用来定义对数空间归约(Log-space reduction,Log-空间规约)。对数空间归约指仅使用对数空间的确定型图灵机进行的规约。区别于常见的多项式时间规约,对数空间规约只允许DTM使用若干个log n(n是输入长度)空间。对数空间规约在定义NL-完全(NLC,NL-complete)问题时候起作用。

L是NL的子集,NL是可以被非确定型图灵机利用对数空间解决的判定问题集合。利用萨维奇定理的建构式证明,可得证NL包含在复杂度P之内,也就是可以被确定型图灵机在多项式空间解决的判定问题集合中。

存在几个已知的NL-完全问题,如2SAT(英语:2-satisfiability)。

根据萨维奇定理,我们已知有以下重要性质:

在计算复杂度理论内,RL(Randomized Logarithmic-space,随机对数空间),或者说RLP(Randomized Logarithmic-space Polynomial-time,随机对数空间多项式时间),是一个复杂度类,包含能以概率图灵机,在对数空间与多项式时间之内,在仅有单向容错的状况内解决的问题。此命名法与RP,这个相近但是没有对数空间限制的复杂度类是雷同的。

在定义RL时的概率图灵机,不会在回答YES的时候犯错。但是允许在回答NO的时候有小于1/3的犯错机会;这种容纳错误的方式被称作(one-sided error)。这里的1/3不是一个绝对的数值;任何符合SC包含一般图灵机以多项式时间和多项式对数空间解决的问题;换句话说,给予一般机器多项式对数的空间,则可以模拟机率图灵机使用对数空间的能力。

一般相信RL = L,换句话说,概率图灵机不会在对数空间下比确定型图灵机更强,多项式时间对数空间的计算方式可以完全的去随机化。这猜想的一个主要证据由Reingold et al.在2005年提出。这问题的证明在无条件去随机化里面可以说是一个被追寻的圣杯。这问题其中一个重大迈进是Omer Reingold证明了SL = L。

在计算复杂度理论,SL(Symmetric Logspace,对称对数空间),是一个复杂度类,是能被对称图灵机(英语:Symmetric Turing machine)在对数空间下解决的判定问题的集合。其存在以下重要性质:

USTCON问题(undirected s-t connectivity,关于无向图两点之间是否存在一个路径的问题)作为一个SL完全(SLC,SL-complete)的SL下的重要特例,通常和SL本身被一起讨论。

2004年10月Omer Reingold成功证明USTCON问题属于L,因为USTCON问题属于SL完全,这便等于证明了SL = L。即,SL是L的一种变体。

相关

  • 关联在概率论和统计学中,相关(Correlation),显示两个随机变量之间线性关系的强度和方向。在统计学中,相关的意义是用来衡量两个变量相对于其相互独立的距离。在这个广义的定义下,有许
  • 坪林区坐标:24°56′15″N 121°42′40″E / 24.937388°N 121.711185°E / 24.937388; 121.711185坪林区(台湾话:.mw-parser-output .sans-serif{font-family:-apple-system,BlinkMa
  • 今文经学今文经学,汉代经学一派,与古文经学相对应,主要特点是加入大量的占卜、阴阳学说,提倡天人感应,以符合当时的需要,被列入学官,成为正统。而古文经学不断对其发动挑战,到汉朝灭亡和南北
  • CD63n/an/an/an/an/an/an/an/an/an/aCD63是一种蛋白质抗原,在人体中由CD63基因编码。CD63主要出现在细胞外囊泡的表面,也会出现在普通的细胞膜表面。透膜四超家族(transmembrane 4
  • 世界大百科事典 (日本)《世界大百科事典》(せかいだいひゃっかじてん)是平凡社出版的日文百科全书,是日本两大百科全书之一(另一套是《日本大百科全书》)。现在是最全面最新的日文百科全书。现时《世界
  • 苏丹公民签证要求部分国家给予苏丹护照持有者豁免签证或落地签证待遇, 苏丹公民如欲入境这些国家,无需提前申请签证。安提瓜和巴布达 · 阿根廷 · 阿鲁巴 · 巴哈马 · 巴巴多斯 · 伯
  • 阿玛斯阿玛斯(A.H. Almaas),是哈弥·阿里(A. Hameed Ali)的笔名。1944年生于科威特。作者、灵性导师,书写及教导关于以现代心理学为基础的灵性开展,并将此治疗称为“钻石途径”。The Diam
  • 巴生县巴生县(马来语:Daerah Klang)是位于雪兰莪州的一个县,位于州的西部。该县北临瓜拉雪兰莪县,东临八打灵县,南临瓜拉冷岳县,西临马六甲海峡。该县面积为626.78平方公里,海岸线长度为73
  • KolourPaintKolourPaint是KDE桌面下的一个位图编辑器,为自由软件。它是针对普通用户提供一个简单图像处理的功能,包含绘图工具、选取工具、线条工具等,也具备自动裁剪、颜色反转、缩放、对
  • EnergyEnergy是台湾以舞蹈著名的男子团体,于2002年7月12日成立,团员擅长街舞,当时堪称“最杀的舞蹈男团”。2002年成立时有五位成员,直至2003年7月,成员TORO(郭苇昀)因经纪人纠纷而离开团