L (复杂度)

✍ dations ◷ 2025-08-25 03:10:12 #数学中未解决的问题,复杂度类,概率复杂度类,闭包算子,计算机科学中未解决的问题

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

相关

  • 航天技术航天技术,又称太空技术(英语:space technology),是一项探索、开发和利用太空以及地球以外天体的综合性工程技术。是一个国家现代技术综合发展水平的重要标志。可以分为民用和军用
  • C05A·B·C·D·G·H·QI·J·L·M·N·P·R·S·VATC代码C05(血管保护药)是解剖学治疗学及化学分类系统的一个药物分组,这是由世界卫生组织药物统计方法整合中心(The WHO Collabor
  • 加拿大上议院加拿大政府与政治 系列条目加拿大君主 (女皇伊莉莎伯二世)枢密院政府现今国会 (第43届) 加拿大上议院加拿大下议院议会选区 选举制度 最新选举最高法院其余次级联邦法院 《加拿
  • 王 珍王珍(?-1721年),字雄樵,山西长治人,清朝官员。王珍台湾知府任内因纵容儿子横征暴敛,引爆了朱一贵事件,后卒于任内。康熙二十年(1681年)辛酉科副贡。康熙五十五年(1716年)由刑部贵州司郎中
  • 氧的同位素氧(原子量:15.9994)共有18种同位素,其中有3种是稳定的。氧的3种稳定同位素是16O、17O、18O,其中16O最多,丰度为99.762 atom%。16O的丰度最大可以由恒星进化论解释。大爆炸产生宇宙
  • 柱色谱法柱色谱法(英语:Column chromatography,又称为柱层析,俗称过柱子)是一种制备性色谱(Preparative chromatography),在化学中是最为常用的从混合物中分离纯净物的分离方法。不同蛋白质
  • 安悦溪安悦溪 (1989年6月10日-),出生于山东潍坊,2007级北京舞蹈学院音乐剧系本科毕业。中国大陆影视女演员。代表作品有《花千骨》、《旋风少女2》,曾为北京儿童艺术剧院演员。1.《花千
  • 弗兰克·富卡里诺弗兰克·A·富卡里诺(英语:Frank A. Fucarino,1920年7月24日-2012年4月3日),为美国NBA联盟的前职业篮球运动员。
  • 安圣基安圣基(韩语:안성기,1952年1月1日-),韩国男演员,曾多次夺得韩国三大影视奖(百想艺术大赏、青龙电影奖及大钟奖),享有“国民影帝”的美誉。童星出身的安圣基在首尔出生,7岁时主演电影《1
  • 陈忠 (成化乙未进士)陈忠(1442年-?),字思敬,山东青州府莒州人,民籍,明朝政治人物。早年出身州学生,山东乡试第二十三名。成化十一年(1475年),参加乙未科会试,得贡士第一百十八名。殿试登进士第三甲第一百零一