Coherence of Reducibilities with Randomness Notions
Coherence of Reducibilities with Randomness Notions
复制标题
DOI：
10.1007/s00224-017-9752-2
复制
发表时间：
2018-10
影响因子：
0.5
通讯作者：
Kenshi Miyabe
中科院分区：
文献类型：
--
作者：
Kenshi Miyabe
粗略地说，当A比BandBis“随机”时，则A应该是随机的。算法随机性理论有“随机”集和“更随机”集的一些公式。在本文中，我们研究了(R，r)对随机概念和可约性具有如下性质：如果Aisr-可约化为带Aisr-随机，则B-随机。答案取决于Randr的观念。这一影响适用于大多数配对，但不适用于某些配对。我们还给出了n-随机性的复杂性刻画。
Loosely speaking, whenAis “more random” thanBandBis “random”, thenAshould be random. The theory of algorithmic randomness has some formulations of “random” sets and “more random” sets. In this paper, we study which pairs (R,r) of randomness notionsRand reducibilitiesrhave the follwing property: ifAisr-reducible toBandAisR-random, thenBshould beR-random. The answer depends on the notionsRandr. The implications hold for most pairs, but not for some. We also give characterizations ofn-randomness via complexity.