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)), 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. 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 n) ⊊ DSPACE(log n) for all integers d > 0. If polyL had a complete problem, call it A, it would be an element of DSPACE(log n) for some integer k > 0. Suppose problem B is an element of DSPACE(log n) but not of DSPACE(log n). The assumption that A is complete implies the following O(log n) space algorithm for B: reduce B to A in logarithmic space, then decide A in O(log n) space. This implies that B is an element of DSPACE(log 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.
References
- Papadimitriou, Christos H. (1994), Computational Complexity, Addison-Wesley, p. 405, ISBN 9780201530827
- Complexity Zoo: polyL
- ^ Ferrarotti, Flavio; González, Senén; Schewe, Klaus-Dieter; Torres, José Maria Turull (2022), "Uniform polylogarithmic space completeness", Frontiers in Computer Science, 4: 845990, doi:10.3389/FCOMP.2022.845990
| P ≟ NP | This theoretical computer science–related article is a stub. You can help Misplaced Pages by expanding it. |