computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by ...

, polyL is the

complexity class In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory. In general, a complexity class is defined in terms of ...

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 of the input values. An example of a decision problem is deciding by means of an algorithm whethe ...

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 algori ...

by an algorithm whose space complexity is bounded by a

polylogarithmic In mathematics, a polylogarithmic function in is a polynomial in the logarithm of , : a_k (\log n)^k + a_ (\log n)^ + \cdots + a_1(\log n) + a_0. The notation is often used as a shorthand for , analogous to for . In computer science, poly ...

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. 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 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 In computational complexity theory, L (also known as LSPACE or DLOGSPACE) is the complexity class containing decision problems that can be solved by a deterministic Turing machine using a logarithmic amount of writable memory space., Definition& ...

many-one reduction In computability theory and computational complexity theory, a many-one reduction (also called mapping reduction) is a reduction which converts instances of one decision problem L_1 into instances of a second decision problem L_2 where the instan ...

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'') \ 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.

External links

* {{comp-sci-theory-stub Complexity classes