PolyL
在計算複雜度理論內，PolyL是一個決定性問題的複雜度類， 可以使用決定型圖靈機使用被某個輸入大小的多对数函数(polylogarithmic)函数所限制的空間。換句話說，polyL = DSPACE((log n)O(1))，這裡的 O(1)代表一個常數。
相對於已知包含在P內的L，我們尚且不知道是否polyL是包含於P內，或者反過來。(PolyL已知包含於QP，或說，類多項式時間(Quasi-polynomial time)之內)。 話說回來，我們知道polyL ≠ P，因為(舉例來說) polyL並沒有在多對一對數空間歸約之下的完備問題。[1] 但是P則有這類問題。PolyL沒有對數空間之下的完備問題是因為空間譜系理論(space hierarchy theory)保證了DSPACE((log n)1) ⊊ DSPACE((log n)2) ⊊ DSPACE((log n)3)…等等。如果polyL有完備問題，則這問題必然落在某個DSPACE((log n)k)內(k為某個常數)。這會令PolyL，也就是包含DSPACE((log n)k+1)以上所有空間複雜度內的問題，全部可以歸約為DSPACE((log n)k)，而違背了空間譜系理論。
參考資料
- ^ Complexity Zoo: polyL
| ||||||||||||||||||||||||||||||||||||
