计算复杂度理论内,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),而违背了空间谱系理论。

参考资料

编辑