computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem ...

, polyL is the

complexity class In computational complexity theory, a complexity class is a set (mathematics), set of computational problems "of related resource-based computational complexity, complexity". The two most commonly analyzed resources are time complexity, time and s ...

decision problem In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question on a set of input values. An example of a decision problem is deciding whether a given natura ...

s that can be solved on a

deterministic Turing machine A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algor ...

by an algorithm whose

space complexity The space complexity of an algorithm or a data structure is the amount of memory space required to solve an instance of the computational problem as a function of characteristics of the input. It is the memory required by an algorithm until it exec ...

is bounded by a polylogarithmic function in the size of the input. In other words, polyL =

DSPACE DSpace is an open source repository software package typically used for creating open access repositories for scholarly and/or published digital content. While DSpace shares some feature overlap with content management systems and document manag ...

((log ''n'')^O(1)), 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 In computational complexity theory, a computational problem is complete for a complexity class if it is, in a technical sense, among the "hardest" (or "most expressive") problems in the complexity class. More formally, a problem ''p'' is called h ...

under logarithmic space

many-one reduction In computability theory and computational complexity theory, a many-one reduction (also called mapping reduction) is a reduction that converts instances of one decision problem (whether an instance is in L_1) to another decision problem (whether ...

s but polyL does not due to the space hierarchy theorem. The space hierarchy theorem guarantees that DSPACE(log^d ''n'') ⊊ DSPACE(log^{d + 1} ''n'') for all integers d > 0. If polyL had a complete problem, call it ''A'', it would be an element of DSPACE(log^k ''n'') for some integer k > 0. Suppose problem ''B'' is an element of DSPACE(log^{k + 1} ''n'') but not of DSPACE(log^k ''n''). The assumption that ''A'' is complete implies the following O(log^k ''n'') space algorithm for ''B'': reduce ''B'' to ''A'' in logarithmic space, then decide ''A'' in O(log^k ''n'') space. This implies that ''B'' is an element of DSPACE(log^k ''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 Stephen Arthur Cook (born December 14, 1939) is an American-Canadian computer scientist and mathematician who has made significant contributions to the fields of complexity theory and proof complexity. He is a university professor emeritus at ...

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.

References

{{comp-sci-theory-stub Complexity classes