L (複雜度)維基百科,自由的 encyclopedia L也稱為LSPACE或DLOGSPACE,是计算复杂度理论中能被确定型图灵机利用對數空间解决的判定问题集合。[1][2] 未解決的数学問題:L = P成立吗? 未解決的数学問題:L = NL成立吗? 对数空间是指与输入规模成对数大小关系的可写的储存空间,大多数对数空间(LOGSPACE)算法以这种方式储存。[1] 重要的相關未解問題包括複雜度類L和P是否恆等(L = P)及複雜度類L和NL是否恆等(L = NL)。 目前已知有以下重要性质: L ⊆ NL ⊆ P NC1 ⊆ L ⊆ NL ⊆ NC2[3]
L也稱為LSPACE或DLOGSPACE,是计算复杂度理论中能被确定型图灵机利用對數空间解决的判定问题集合。[1][2] 未解決的数学問題:L = P成立吗? 未解決的数学問題:L = NL成立吗? 对数空间是指与输入规模成对数大小关系的可写的储存空间,大多数对数空间(LOGSPACE)算法以这种方式储存。[1] 重要的相關未解問題包括複雜度類L和P是否恆等(L = P)及複雜度類L和NL是否恆等(L = NL)。 目前已知有以下重要性质: L ⊆ NL ⊆ P NC1 ⊆ L ⊆ NL ⊆ NC2[3]