In computational complexity theory, polyL is the complexity class of decision problems that can be solved on a deterministic Turing machine by an algorithm whose space complexity is bounded by a polylogarithmic function in the size of the input. In other words, polyL = DSPACE((log n)<sup>O(1)</sup>), where n denotes the input size, and O(1) denotes a constant.
Just as L â P, polyL â QP. However, the only proven relationship between polyL and P is that polyL â P; it is unknown if polyL â P, if P â polyL, or if neither is contained in the other. The same is true for polyL vs NP.
One proof that polyL â P is that P has a complete problem under logarithmic space many-one reductions but polyL does not due to the space hierarchy theorem. The space hierarchy theorem guarantees that DSPACE(log<sup>d</sup> n) â DSPACE(log<sup>d + 1</sup> n) for all integers d > 0. If polyL had a complete problem, call it A, it would be an element of DSPACE(log<sup>k</sup> n) for some integer k > 0. Suppose problem B is an element of DSPACE(log<sup>k + 1</sup> n) but not of DSPACE(log<sup>k</sup> n). The assumption that A is complete implies the following O(log<sup>k</sup> n) space algorithm for B: reduce B to A in logarithmic space, then decide A in O(log<sup>k</sup> n) space. This implies that B is an element of DSPACE(log<sup>k</sup> n) and hence violates the space hierarchy theorem.
The lack of complete problems for polyL under logarithmic space many-one reductions has led Ferrarotti et al. to define a different notion of completeness for this class, involving transformations from parameterized problems to polylog-space machines that solve the problems for specific parameter values.
An interesting subclass is SC (Steve's Class, named in honor of Stephen Cook and in analogy with Nick's Class.): The class of decision problems solvable by a Turing machine that simultaneously uses polynomial time and polylogarithmic space. It is obviously a subset of P â© polyL, and might even be strictly smaller than it, since for the latter, it suffices to have two separate algorithms: one polynomial-time and the other polylogarithmic-space, whereas for SC, there must be a single algorithm that satisfies both constraints.
Deterministic context-free languages can be recognized in SC. SC contains Randomized L and Bounded-Error Probabilistic L.