L (复杂度)

✍ dations ◷ 2025-04-26 12:14:37 #数学中未解决的问题,复杂度类,概率复杂度类,闭包算子,计算机科学中未解决的问题

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的一种变体。

相关

  • 促甲状腺素促甲状腺激素,又称TSH(英语:Thyroid-stimulating hormone, TSH or Thyrotropin),是一个由垂体前叶当中的促甲状腺激素细胞所分泌的肽类激素。该激素用于调节甲状腺的内分泌功能.
  • 黑色素细胞癌黑色素瘤,又称恶性黑色素瘤,是一种从黑色素细胞发展而来的癌症,是皮肤癌中罕见的癌症。好发于皮肤但也可能出现在口腔、肠道或眼睛中。女性患者的黑色素瘤最常出现在腿,而男性患
  • 动能动能是物质运动时所得到的能量。它通常被定义成使某物体从静止状态至运动状态所做的功。由于运动是相对的,动能也是相对于某参照系而言。同一物体在不同的参照系会有不同的速
  • 警徽天职《警徽天职》(英文:C.L.I.F. ),新加坡新传媒私人有限公司警匪电视剧,由郑斌辉、戚玉武、白薇秀、 童冰玉、黄俊雄 及李美玲领衔主演。电视剧《警徽天职》以即将举行的国际保安峰
  • S/2003 J 12S/2003 J 12是环绕木星运行的一颗卫星,是已知最小的一颗卫星。它在2003年被由斯科特·谢泼德领导的夏威夷大学一个天文小组发现。S/2003 J 12的直径约1公里,公转轨道的平均半
  • 林阿琴林阿琴(1915年-),是台湾日治时期中胶彩画家之一。1928年就读台北第三高等女学校,师承乡原古统学习胶彩画,即展露绘画才华。也因为乡原古统的介绍,林阿琴认识郭雪湖于1935年春天在圆
  • 珠儿珠儿·克尔奇(英文:, 1974年5月23日-),艺名珠儿,美国创作歌手、吉他手、演员和诗人。她四次获得格莱美奖提名,专辑的全球销量超过2700万。珠儿的首张专辑《Pieces of You》于1995年2
  • 京都排骨京都排骨,是一道排骨料理,味道酸甜,起源于江浙菜系的无锡,后传播至中国各地。京都排骨与无锡排骨接近,类似的做法还有淮扬菜的糖醋排骨。江浙菜以甜味烹调见长,西湖醋鱼、东坡肉、
  • 蒙特乌贝卡里亚蒙特乌贝卡里亚(意大利语:Montù Beccaria),是意大利帕维亚省的一个市镇。总面积15.6平方公里,人口1746人,人口密度111.9人/平方公里(2009年)。国家统计(ISTAT)代码为018100。
  • 那布·穆金·阿普利那布·穆金·阿普利(约公元前978年—约公元前943年在位)(英语:Nabû-mukin-apli)巴比伦第八王朝国王。他在位36年,不断受到阿拉米亚人入侵,使宗教仪式无法进行,后者在底格里斯河与埃