Probabilistic Constructions of Computable Objects and a Computable Version of Lovász Local Lemma
Probabilistic Constructions of Computable Objects and a Computable Version of Lovász Local Lemma
复制标题
可计算对象的概率构造和 Lovász 局部引理的可计算版本
DOI：
10.3233/fi-2014-1029
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
A. Shen
中科院分区：
文献类型：
--
作者：
A. Rumyantsev;A. Shen
可以使用非构造证明来证明具有某些属性的对象的存在，而无需提供这种对象的明确示例。一种特殊情况是概率证明，我们证明具有所需属性的对象在某些随机过程中以某些正概率出现。我们可以使用此类参数证明存在可计算的无限对象吗？有时是：遵循[8]，我们展示了如何使用layerwise可计算映射的概念来证明Lovasz本地引理的可计算版本。
A nonconstructive proof can be used to prove the existence of an object with some properties without providing an explicit example of such an object. A special case is a probabilistic proof where we show that an object with required properties appears with some positive probability in some random process. Can we use such arguments to prove the existence of a computable infinite object? Sometimes yes: following [8], we show how the notion of a layerwise computable mapping can be used to prove a computable version of Lovasz local lemma.