PolyL (Complexitat)

En teoria de la complexitat, la classe de complexitat PolyL és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing determinista en un espai fitat per una funció polilogarítmica. Per tant es pot dir que PolyL = DSPACE ((log n)^O(1)) on n és la mida de l'entrada i O(1) és una constant.

Relació amb d'altres classes

Igual que L ⊆ P, polyL ⊆ QP.

Tot i això, l'única relació provada entre PolyL i P és que polyL ≠ P i es desconeix si polyL ⊊ P, si P ⊊ polyL o si una conté a l'altra.