PolyL
Encyclopedia
In computational complexity theory
, PolyL is the complexity class
of decision problem
s that can be solved on a deterministic Turing machine whose required space is bounded by some 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.
In contrast to L
, which is contained in P
, it is not known if polyL is contained in P or vice versa. (PolyL is known to be contained in QP or Quasi-polynomial time.) On the other hand, we do know that polyL ≠ P, since (for example) polyL does not have complete problems under many-to-one
logspace reductions
, but P has such complete problems. The reason PolyL does not have complete problems under logspace reductions is that the space hierarchy theorem
guarantees that DSPACE((log n)1) ⊊ DSPACE((log n)2) ⊊ DSPACE((log n)3) and so on. If polyL had a complete problem, it would have to lie in DSPACE((log n)k) for some k. This would put PolyL, and therefore DSPACE((log n)k+1), inside DSPACE((log n)k) violating the space hierarchy theorem.
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, PolyL is the complexity class
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...
of decision problem
Decision problem
In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem...
s that can be solved on a deterministic Turing machine whose required space is bounded by some polylogarithmic
Polylogarithmic
A polylogarithmic function in n is a polynomial in the logarithm of n,In computer science, polylogarithmic functions occur as the order of memory used by some algorithms .All polylogarithmic functions are...
function in the size of the input. In other words, polyL = DSPACE
DSPACE
In computational complexity theory, DSPACE or SPACE is the computational resource describing the resource of memory space for a deterministic Turing machine. It represents the total amount of memory space that a "normal" physical computer would need to solve a given computational problem with a...
((log n)O(1)), where n denotes the input size, and O
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
(1) denotes a constant.
In contrast to L
L (complexity)
In computational complexity theory, L is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a logarithmic amount of memory space...
, which is contained in P
P (complexity)
In computational complexity theory, P, also known as PTIME or DTIME, is one of the most fundamental complexity classes. It contains all decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.Cobham's thesis holds...
, it is not known if polyL is contained in P or vice versa. (PolyL is known to be contained in QP or Quasi-polynomial time.) On the other hand, we do know that polyL ≠ P, since (for example) polyL does not have complete problems under many-to-one
Many-one reduction
In computability theory and computational complexity theory, a many-one reduction is a reduction which converts instances of one decision problem into instances of a second decision problem. Reductions are thus used to measure the relative computational difficulty of two problems.Many-one...
logspace reductions
Reduction (complexity)
In computability theory and computational complexity theory, a reduction is a transformation of one problem into another problem. Depending on the transformation used this can be used to define complexity classes on a set of problems....
, but P has such complete problems. The reason PolyL does not have complete problems under logspace reductions is that the space hierarchy theorem
Space hierarchy theorem
In computational complexity theory, the space hierarchy theorems are separation results that show that both deterministic and nondeterministic machines can solve more problems in more space, subject to certain conditions. For example, a deterministic Turing machine can solve more decision problems...
guarantees that DSPACE((log n)1) ⊊ DSPACE((log n)2) ⊊ DSPACE((log n)3) and so on. If polyL had a complete problem, it would have to lie in DSPACE((log n)k) for some k. This would put PolyL, and therefore DSPACE((log n)k+1), inside DSPACE((log n)k) violating the space hierarchy theorem.