L (複雜度)

维基百科,自由的百科全书
跳转至: 导航搜索

L也稱為LSPACE,是计算复杂度理论中能被确定型图灵机利用對數空間解决的判定问题集合。

LNL的子集合,NL是可以被非確定型圖靈機利用對數空間解决的判定问题集合。利用薩維奇定理的建構式證明,可得證NL包含在复杂度P之內,也就是可以被確定型圖靈機在多項式空間解决的判定问题集合中。因此L ⊆ NL ⊆ P

重要的相關未解問題包括複雜度類L和P是否恆等(L = P)及複雜度類L和NL是否恆等(L = NL)。

功能性問題相關的類別是FL。FL常用來定義對數空間歸約