L (复杂度)

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

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

相关

  • 孟乔森综合征孟乔森综合征(Munchausen syndrome)是指一种通过描述、幻想疾病症状,假装有病乃至主动伤残自己或他人,以取得同情的心理疾病。它还有求医癖、住院癖、佯病症等俗名。此疾病得名
  • 抗磁性抗磁性(Diamagnetism,亦作反磁性)是一些类别的物质,当处在外加磁场中,会对磁场产生的微弱斥力的一种磁性现象。抗磁性的成因,是当物质处在外加磁场中,外加磁场使得物质电子轨道(更精
  • 格拉茨格拉茨(德语:Graz;德语发音:.mw-parser-output .IPA{font-family:"Charis SIL","Doulos SIL","Linux Libertine","Segoe UI","Lucida Sans Unicode","Code2000","Gentium","Gent
  • 1944第十三届夏季奥林匹克运动会(英语:the Games of the XIII Olympiad,法语:les Jeux de la XIIIe Olympiade),原定于1944年在英国伦敦举行。然而因第二次世界大战爆发而停办。 第二
  • 原陆军总医院中国人民解放军军徽中国人民解放军总医院第七医学中心,位于北京市,隶属中国人民解放军总医院。该院成立于1913年,初为中华民国北洋政府时期的陆军军医学校附属医院。后来为南京
  • 拉米拉达拉米拉达(英语:La Mirada),是美国加利福尼亚州洛杉矶县下属的一座城市。建市于1960年3月23日,面积约为7.84平方英里(20.3平方公里)。根据2010年美国人口普查,该市有人口48,527人。拉
  • 医学和医学技术年表这是一份医学和医学技术年表。1. 这些医学技术的具体时间并不确定。 A Tribute to Hinduism suggests that Sushruta lived in the 5th century BC.
  • 大量生产大量生产(德文:Massenproduktion、法文:Production en série、英文:Mass production)简称量产。因为大量生产有降低成本,提高效率的好处,量产之概念很早便在人类社会中出现。但量
  • 腈钠腈钠是指腈类化合物和钠离子形成的盐,这类盐被认为是反应中存在的中间体。腈钠可由腈和氨基钠、取代氨基钠或金属钠反应得到。但由于腈钠的高度不稳定性,其固体的分离特别困难
  • 什拉赫塔什拉赫塔又译成众议院贵族、施拉赤塔(波兰语:,立陶宛语:šlėkta)是广义、狭义下的波兰贵族称谓,包含了波兰王国、立陶宛大公国、以及两国在1569年合并为波兰立陶宛联邦的贵族阶级