When faced with a difficult problem that requires a lot of time and/or space, a useful (but seemingly bizarre) method of dealing with the problem is to relax the requirement that the solution always produces the correct answer. Instead, it might be acceptable for a solution to produce the correct answer say 99.9% of the time.

Accepting this small risk of obtaining an incorrect answer can lead to some dramatic memory and time savings. For example, the problem of determining whether or not a given number is prime (important for cryptography) normally requires exponential time and checking even moderately large numbers with 20-30 digits is infeasible. However, a probabilistic algorithm is able to determine whether numbers with over 100 digits are prime in under 1 minute with very high confidence. The chance of making an error can be made arbitrarily small, and error probabilities of 2^{-40} are not uncommon. In this case, the algorithm is probably more reliable than the computer it runs on!

We use the same principles to produce a probabilistic state generation algorithm based on hash compaction. The algorithm has a very low memory utilization but maintains a high probability of producing the correct state graph. As in the case of the probabilistic prime algorithm, the chance of making an error can be made arbitrarily small.