PolyL

En complejidad computacional, PolyL es una clase de complejidad que contiene aquellos lenguajes para los cuales existe un algoritmo determinista cuyo espacio de decisión requerido está acotado por un polilogaritmo en función del tamaño de la entrada. En otras palabras, polyL = DSPACE((log n)^O(1)), donde n denota el tamaño de la entrada, y O(1) es una constante.

A diferencia de la clase L, que está contenida en P, no se sabe si polyL esté contenida en P, o viceversa. Por otra parte, sabemos que polyL ≠ P.​

Referencias

• Datos: Q7226108