polyL
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)O(1)), where n denotes the input size, and O(1) denotes a constant.[1]
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.[2][3]
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(logd n) ⊊ DSPACE(logd + 1 n) for all integers d > 0. If polyL had a complete problem, call it A, it would be an element of DSPACE(logk n) for some integer k > 0. Suppose problem B is an element of DSPACE(logk + 1 n) but not of DSPACE(logk n). The assumption that A is complete implies the following O(logk n) space algorithm for B: reduce B to A in logarithmic space, then decide A in O(logk n) space. This implies that B is an element of DSPACE(logk n) and hence violates the space hierarchy theorem.[4]
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.[4]
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.[5] SC contains Randomized L and Bounded-Error Probabilistic L.[6]
References
[edit]- ^ Papadimitriou, Christos H. (1994), Computational Complexity, Addison-Wesley, p. 405, ISBN 9780201530827
- ^ Book, Ronald V. (1976-02-01). "Translational lemmas, polynomial time, and (log n)j-space". Theoretical Computer Science. 1 (3): 215–226. doi:10.1016/0304-3975(76)90057-8. ISSN 0304-3975.
- ^ Complexity Zoo: polyL
- ^ a b 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
- ^ Cook, Stephen A. (1979-04-30). "Deterministic CFL's are accepted simultaneously in polynomial time and log squared space". Proceedings of the eleventh annual ACM symposium on Theory of computing - STOC '79. New York, NY, USA: Association for Computing Machinery. pp. 338–345. doi:10.1145/800135.804426. ISBN 978-1-4503-7438-5.
- ^ Nisan, Noam (1994-03-01). "RL ⊆ SC". Computational Complexity. 4 (1): 1–11. doi:10.1007/BF01205052. ISSN 1420-8954.