Multi-Access Randomness Saves Space, Even for Halting Algorithms

We prove that every language in $\mathsf{P}^{\# \mathsf{P}}$ can be decided by a bounded-error randomized algorithm that uses only $O(\log n)$ bits of work space. The algorithm is guaranteed to halt for every input and every setting of the random tape. However, there is a catch: the algorithm uses a multi-access random tape, i.e., the algorithm scans both forward and backward across a read-only tape filled with an unlimited number of random bits. Prior work on log-space algorithms with multi-access randomness either focuses on polynomial-time algorithms, or else permits algorithms that sometimes run forever. Our algorithm always halts, but it uses exponential time. Thus, our work identifies a natural model of computation in which randomness is intrinsically useful, assuming $\mathsf{L} \neq \mathsf{P}^{\# \mathsf{P}}$.

We show that certain problems can be solved using randomness and a small amount of memory. Solving these same problems deterministically would probably require a large amount of memory, so this is a case where algorithms with randomness are apparently more powerful than algorithms without randomness.

A subtlety is that you can't run our algorithm if your only source of randomness is a coin that you can flip. Instead, our algorithm requires access to a large database of pre-generated random bits. That way, it can go back and re-read old random bits as many times as it wants.

An algorithm with similar properties to ours has been known since the 1980s, but the old algorithm has a weakness, which is that it is not guaranteed to halt. Sometimes it runs forever without ever producing an output. Our new algorithm always halts.