It is not, however, known or believed to be equal to or , the polynomial-time restrictions of and which some authors refer to as and . We can relate to deterministic space using Savitch's theorem, which tells us that any nondeterministic algorithm can be simulated by a deterministic machine in at most quadratically more space. From Savitch's theorem, we have directly that:  This was the strongest deterministic-space inclusion known in 1994 (Papadimitriou 1994 Problem 16.4.10, "Symmetric space"). Since larger space classes are not affected by quadratic increases, the nondeterministic and deterministic classes are known to be equal, so that for example we have . Suppose "C" is the complexity class of decision 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: 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 2"n" 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 2"n". 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 2"n" 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.