论文标题
在动态编程中翻转硬币几乎没有用
Coin Flipping in Dynamic Programming is Almost Useless
论文作者
论文摘要
我们考虑在实际数字上使用的概率电路，并使用有限描述复杂性作为门的任意半缘函数。特别是，这样的电路可以使用所有算术操作 +， - ，x， /，优化操作最小和最大，有条件的分支（如果是else）等等。我们表明，使用这些操作中的任何一个作为门的概率电路可以通过确定性电路模拟，只有大约二次爆炸。当降低近似电路时，还显示了电路尺寸的爆炸不大。激发标题的算法后果是，随机性不能实质上加快动态编程算法。
We consider probabilistic circuits working over the real numbers, and using arbitrary semialgebraic functions of bounded description complexity as gates. In particular, such circuits can use all arithmetic operations +, -, x, /, optimization operations min and max, conditional branching (if-then-else), and many more. We show that probabilistic circuits using any of these operations as gates can be simulated by deterministic circuits with only about a quadratical blowup in size. A not much larger blow up in circuit size is also shown when derandomizing approximating circuits. The algorithmic consequence, motivating the title, is that randomness cannot substantially speed up dynamic programming algorithms.
