Talk:Randomized Algorithms (Spring 2010)

请大家点击页面上方的“edit”进行留言和讨论 --etone 13:08, 11 January 2010 (UTC)

---

尹老师，你好！上次去听了你的randomized algorithms的课，很不错。但有几点疑问，描述如下： 1、你课件上说randomized algorithms有个特性是“简单”，能否举个例子，最好能跟这个例子的deterministic algorithms做下比较。 2、monte carlo式的randomized algorithms的结果怎么验证？比如min-cut这个例子，假设独立地执行karger算法10次，其中有一次结果是正确的，10次结果如下： F,F,F,F,T,F,F,F,F,F(T为正确，F为错误),问题是我怎么知道第5次是正确的。甚者，如果执行n（n比较大）才能得到一次正确结果，即使是人工验证也是很难的。不知道是否想错误了。 望老师有空解答下。

Re:

(1) randomized algorithm算法简单的例子有很多，例如karger algorithm明显就比确定算法计算min-cut的最大流算法简单。以后还会看到更多。

(2)课上讲的是：如果可以高效的检验结果的正确性，则poly-time monte carlo algorithm可以通过反复“尝试-验证”的方法转换为expected poly-time las vegas algorithm。

假如无法高效的检验结果的正确性，则该方法就不行了。例如你说的karger algorithm计算min-cut，我们不知道如何高效的检验一个cut是否最小，所以无法最终确定正确。课堂上讲了，通过反复运行，取所有返回cut中最小的一个cut，我们可以把error probability缩小到足够小，但无法缩小到0，即无法完全确定结果真的正确。（实际上，由于min-cut是P问题，我们可以运行最大流算法去确定地计算min-cut，和karger algorithm返回的cut比较就知道是否正确。理论上讲，这也算“验证”了结果的正确性，但这显然不是你的原意）

如果对于任何问题人类都知道怎么高效验证一个解的正确性，那么高效monte carlo算法就等同于高效las vegas算法，于是就有ZPP=RP=BPP了。然而目前这还是未知的。

--etone 10:07, 18 March 2010 (UTC)