In computational complexity theory, PolyL is the complexity class of decision problems that can be solved on a deterministic Turing machine whose required space is bounded by some polylogarithmic function in the size of the input. In other words, polyL = DSPACE((log n)O(1)), where n denotes the input size, and O(1) denotes a constant.
In contrast to L, which is contained in P, it is not known if polyL is contained in P or vice versa. (PolyL is known to be contained in QP or Quasi-polynomial time.) On the other hand, we do know that polyL ≠ P, since (for example) polyL does not have complete problems under many-to-one logspace reductions,[1] but P has such complete problems. The reason PolyL does not have complete problems under logspace reductions is that the space hierarchy theorem guarantees that DSPACE((log n)1) ⊊ DSPACE((log n)2) ⊊ DSPACE((log n)3) and so on. If polyL had a complete problem, it would have to lie in DSPACE((log n)k) for some k. This would put PolyL, and therefore DSPACE((log n)k+1), inside DSPACE((log n)k) violating the space hierarchy theorem.