You are correct that approximate and random algorithms are quite different. An approximate algorithm is one that is guaranteed to give a solution that's approx

You are correct that approximate and random algorithms are quite different. An approximate algorithm is one that is guaranteed to give a solution that's approximate to within a in some sense, such as within a multiplicative factor of k, but in a deterministic time (generally polynomial). So, for instance, you could solve the TSP within 3/2 of the optimal length using Chrisofides algorithm[0]. In contrast, a randomized algorithm in RP is one which is guaranteed to be able to tell you whether there is no solution with 100% accuracy, but, if it says a solution exists, it is only correct to within some probability p. [1] A good example here is the Miller-Rabin primality test. [2,3] --- [0]: https://en.wikipedia.org/wiki/Christofides_algorithm https://en.wikipedia.org/wiki/Christofides_algorithm [1]: https://en.wikipedia.org/wiki/RP_(complexity) https://en.wikipedia.org/wiki/RP_(complexity) [2]: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality... [3]: Incidentally, although it's a little obscure, I did once manage to dig up the original paper that contained the elements of this algorithm. It was quite readable, IIRC. I may see if I can find it to post later.