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]