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)¹) ⊊ DSPACE((log n)²) ⊊ DSPACE((log n)³)…等等。如果polyL有完备问题，则这问题必然落在某个DSPACE((log n)^k)内(k为某个常数)。这会令PolyL，也就是包含DSPACE((log n)^k+1)以上所有空间复杂度内的问题，全部可以归约为DSPACE((log n)^k)，而违背了空间谱系理论。