Probabilistic computability and choice
Probabilistic computability and choice
复制标题
概率计算和选择
DOI：
10.1016/j.ic.2015.03.005
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
R. Hölzl
中科院分区：
文献类型：
--
作者：
V. Brattka;G. Gherardi;R. Hölzl
我们研究的计算能力的随机计算的无限对象，如真实的数字。特别是，我们介绍了一个拉斯维加斯可计算的多值函数的概念，这是一个函数，可以计算的概率图灵机，接收随机二进制序列作为辅助输入。机器可以利用这个随机序列，但它总是必须产生一个正确的结果，或者如果随机建议不成功，则在有限时间后停止计算。在正概率的情况下，随机建议必须成功。利用概率选择原理和弱弱Kynig引理刻画了Weihrauch格上的拉斯维加斯可计算函数类.除其他事项外，我们证明了一个独立选择定理，这意味着拉斯维加斯可计算功能下的组成。在一个案例研究中，我们表明，纳什均衡是拉斯维加斯可计算的，而零的符号变化的连续函数不能计算在拉斯维加斯机。然而，我们发现，后者的问题承认随机算法较弱的故障识别机制。最后一个结果可以解释为：介值定理可归结为弱弱Kynig引理的跳跃，而不是弱弱Kynig引理本身。这些例子还证明了拉斯维加斯可计算函数形成了可计算函数类的真超类和非确定性可计算函数类的真子类。我们还研究了特定的下界对成功概率的影响，这导致了严格的类层次结构。特别是，概率放大的经典技术在无限对象的计算中失败了。我们还研究了对潜在概率空间的依赖性。除Cantor空间外，我们还研究了自然数、欧氏空间和Baire空间。
We study the computational power of randomized computations on infinite objects, such as real numbers. In particular, we introduce the concept of a Las Vegas computable multi-valued function, which is a function that can be computed on a probabilistic Turing machine that receives a random binary sequence as auxiliary input. The machine can take advantage of this random sequence, but it always has to produce a correct result or to stop the computation after finite time if the random advice is not successful. With positive probability the random advice has to be successful. We characterize the class of Las Vegas computable functions in the Weihrauch lattice with the help of probabilistic choice principles and Weak Weak Kőnig's Lemma. Among other things we prove an Independent Choice Theorem that implies that Las Vegas computable functions are closed under composition. In a case study we show that Nash equilibria are Las Vegas computable, while zeros of continuous functions with sign changes cannot be computed on Las Vegas machines. However, we show that the latter problem admits randomized algorithms with weaker failure recognition mechanisms. The last mentioned results can be interpreted such that the Intermediate Value Theorem is reducible to the jump of Weak Weak Kőnig's Lemma, but not to Weak Weak Kőnig's Lemma itself. These examples also demonstrate that Las Vegas computable functions form a proper superclass of the class of computable functions and a proper subclass of the class of non-deterministically computable functions. We also study the impact of specific lower bounds on the success probabilities, which leads to a strict hierarchy of classes. In particular, the classical technique of probability amplification fails for computations on infinite objects. We also investigate the dependency on the underlying probability space. Besides Cantor space, we study the natural numbers, the Euclidean space and Baire space.