随机算法是建设性的吗？

Question

从概率方法中，通常认为通过概率方法的证明是非构造性的。

但是，概率方法的证明确实设计了一种随机算法，并将其用于证明存在。从P103引用 Rajeev Motwani的随机算法，Prabhakar Raghavan:

我们可以通过概率方法将证据视为一种随机算法。然后，这将需要进一步的分析，以限制算法未能在给定执行上找到良好分区的概率。概率方法中的思想实验与随机算法之间的主要区别在于每个产量的终点。当我们使用概率方法时，我们只关心表明存在组合对象存在。因此，我们满足于表明出现非零概率发生的有利事件。另一方面，使用随机算法，效率是一个重要的考虑因素 - 我们不能忍受微小的成功概率。

因此，我想知道是否将随机算法视为不建设性，尽管它们确实在每次运行的末尾输出了一个解决方案，这可能是理想的解决方案。

如何定义算法或证明是如何定义的？

谢谢！

Answer 1

概率方法通常用于表明 一些 具有特定属性的随机对象非零，但没有显示任何示例。它确实可以保证“重复启用”算法最终将终止，但不会在运行时给出上限。因此，除非财产持有的概率是实质性的，否则概率方法的存在证明是非常差的算法。

实际上，概率算法实际上并不是建设性的证据，而是它们是算法 生产 建设性的存在证明。输出是旨在证明存在的物体的对象；但是它将 最终 产生一个（“将存在一个迭代，其中它产生一个例子 - 除了零概率...“）不足以具有建设性；对于那些已经接受了存在非零概率的人而言，这只会满意。相反，如果您确实对运行时间有良好的束缚，那么原则上没有任何借口不运行它来实际产生一个例子。好的概率算法仍然不是建设性的证据，而是一个好的证据 计划 获得建设性证明。

请注意，这个想法，随机算法是一个 证明策略 （与自身的证据相反）证明存在量化，这与归纳是一种良好的证明策略（在自然数量上）的良好证明策略没有什么不同。这种类比似乎令人信服，因为归纳本质上是递归作为计算技术的核心。 （对于任何正整数$ n $ $是$ 2N-1 $之前的连续奇数总数的总和。但是，诱导被建设性地接受，因为它已经是Peano算术的公理（-scheme），并且它与其他公理无关。相比之下，没有推理或公理规则可以使概率方法建设性地证明存在，或者建设性地证明概率算法会产生存在的证据，或者沿这些线路产生任何东西。您根本无法证明有一类对象的例子是从一个概率算法来构造它的事实，除非您已经接受该命题是公理或其他前提。

当然，一个人可能会采用哲学立场，中间是建构主义和经典的生存方法，并说一个人想要的不是建构本身本身，而是建筑 - 施加机构，而施工造口允许在任何概率小于一个的概率上失败。这将使任何概率结构都“示意图”，即使不是完全建设性。在人们希望划清界限的地方，说他们找到了存在的“令人满意的”证明，最终取决于他们希望从证据中获得的直觉（从非哲学意义上）。

Answer 2

统一的证明复杂性是一个专门的领域（除其他）研究了建设性的证明概念及其与复杂性类别的关系。对于每个流行的（统一）电路复杂性类别，都可以定义一个理论，在该理论中，可证明的所有事物在此复杂性类别中具有“支持”。随机算法是通过Pigonhole原理的版本来容纳的（奇怪的是）。

不幸的是，我不是专家 厨师和nguyen （与库克定理中的库克相同）和 埃米尔·杰瓦贝克, ，尤其是他的 论文 在随机计算上。