1
$\begingroup$

For example, in the definition of BPL, we require that the probabilistic Turing machine has to halt for every input and every randomness. What is the reason for us to define them this way? What would happen if they don't halt? On the other hand, we don't require space-bounded non-deterministic Turing machines to halt.

$\endgroup$

1 Answer 1

1
$\begingroup$

This is a very old question, but is a good question and deserves an answer.

The basic issue is that if we let the probabilistic algorithm run for an unbounded amount of time (and randomness), it can solve NL in a trivial way. In fact, it can solve NL in RL, and even ZPL. But it does so by running in an exponential amount of time, which doesn't feel fair.

The idea of the algorithm is simple: store the current state, ask for the next state transition. If the transition is invalid, restart. Otherwise, transition to that state. If we ever transition from the start state to an accept state, accept. Since we know that NL = coNL, each time we restart, switch between the NL and coNL statement. Clearly this algorithm only uses logarithmic space, never outputs the wrong answer, and every time it runs has a 1/exp(n) chance of outputting the right answer. So after an expected exponential amount of time, we output the right answer with high probability.

And if we give two way access to the randomness and unbounded time/randomness, it gets even worse, allowing us to run the same idea but with polynomial length states, giving us BPSPACE is in ZPL.

In contrast, we don't require NL algorithms to halt because a non halting nondeterministic algorithm can be turned into one. If a path to the accepting vertex exists, it is reachable in polynomial time. Thus we can just reject if we didn't find this shortest route to the accept vertex. This only requires holding a counter, which only takes logarithmic space and polynomial time. Unfortunately, our BP algorithm for NL does not accept within polynomial time with high probability.

For reference, see Nisan's "On read-once vs. multiple access to randomness in logspace".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.