|
|
|
|
|
Zpl - This article is about the complexity class. For the programming language, see ZPL programming language.
In complexity theory, ZPL (Zero-error Probabilistic Logarithmic space) is the set of problems solvable by a probabilistic Turing machine which always yields the correct answer and uses logarithmic space on average. Probabilistic algorithms that always give the correct answer are called Las Vegas algorithms. A surprising result is that ZPL is equal to both RL and NL; thus, if a problem can be solved in logarithmic space with nondeterminism or with one-sided error, it can be solved with no error and logarithmic space on average. See the articles on RL and NL for more information about ZPL.
|
 |
|
| Copyright 2005-2009 OnPedia.com. All Rights Reserved |
|
|