4 ms·

Vertex Cover is a well known problem that can be dropped to polynomial time with a random approximate algorithm. I'm not entirely sure if approximate algorithm

Vertex Cover is a well known problem that can be dropped to polynomial time with a random approximate algorithm. I'm not entirely sure if approximate algorithms are included in RP.

contravariant 6y ago
To my understanding an approximate algorithm is one that technically solves a different problem. I don't think the approximate algorithms themselves form a complexity class because it's not sufficiently well defined how close an approximation is for an arbitrary problem. So it doesn't really make sense to ask if approximate algorithms are included in RP. Although I suppose you could consider RP to be an approximate algorithm for a decision problem, although it doesn't guarantee it's close it just guarantees it's right at least x% of the time.
- pmiller2 6y ago
  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.
musicale 6y ago
A polynomial approximate algorithm is nice, but to actually solve the problem correctly/optimally don't you need a polynomial exact algorithm?

Vertex Cover is a well known problem that can be dropped to polynomial time with a random approximate algorithm. I'm not entirely sure if approximate algorithms are included in RP.

contravariant 6y ago

To my understanding an approximate algorithm is one that technically solves a different problem. I don't think the approximate algorithms themselves form a complexity class because it's not sufficiently well defined how close an approximation is for an arbitrary problem. So it doesn't really make sense to ask if approximate algorithms are included in RP. Although I suppose you could consider RP to be an approximate algorithm for a decision problem, although it doesn't guarantee it's close it just guarantees it's right at least x% of the time.

pmiller2 6y ago
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.

musicale 6y ago

A polynomial approximate algorithm is nice, but to actually solve the problem correctly/optimally don't you need a polynomial exact algorithm?