NL (complexity) - Probabilistic Definition

Probabilistic Definition

Suppose C 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. The constant 1/3 is arbitrary; any x with 0 ≤ x < 1/2 would suffice.

It turns out that C = NL. Notice that C, 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. If we do limit it to polynomial time, we get the class RL, which is contained in but not known or believed to equal NL.

There is a simple algorithm which establishes that C = NL. Clearly C 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 a C algorithm accepts along at least two-thirds of its computation paths.

To show that NL is contained in C, 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 (bounded below by a constant).

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 2n steps on average 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.