|
|
|
|
|
Rl - This article is about the complexity class; for the acronym used on the Internet, see real life. For the R&B singer, see Next (band).
In computational complexity theory, RL is the complexity class of problems solvable in logarithmithic space with probabilistic Turing machines that never accept incorrectly but are allowed to reject incorrectly less than 1/3 of the time; this is called one-sided error. Some authors also require that the machine take polynomial time, but we refer to this restricted class as RLP. The constant 1/3 is arbitrary; any x with 0 ≤ x < 1/2 would suffice. It is known that RL, with this definition, is equal to both NL, the class of problems solvable using a nondeterministic Turing machine in log space, and ZPL, the class of randomized algorithms that commit no error and run in log space on average. Notice that RL, unlike its deterministic counterpart L, is not limited to polynomial time, because although it has a polynomial number of configurations it can use randomness to escape an infinite loop. There is a simple algorithm which establishes that RL = NL. Clearly RL is contained in NL, since: - If the string is not in the language, both reject along all computation paths.
- If the string is in the language, an NL algorithm accepts along at least one computation path and an RL algorithm accepts along at least two-thirds of its computation paths.
To show that NL is contained in RL, we simply take an NL algorithm and choose a random computation path of length n, and do this 2n times. Because no computation path exceeds length n, and because there are 2n computation paths in all, we have a good chance of hitting the accepting one. The only problem is that we don't have room in log space for a binary counter that goes up to 2n. To get around this we replace it with a randomized counter, which simply flips n coins and stops and rejects if they all land on heads. Since this event has probability 2-n, we expect to take about 2n steps before stopping. It only needs to keep a running total of the number of heads in a row it sees, which it can count in log space. Thus, when we only look at space alone, it seems that randomization and nondeterminism are equally powerful. See the article on NL for more properties of the class and some of its complete problems. References
|
 |
|
| Copyright 2005-2009 OnPedia.com. All Rights Reserved |
|
|