论文标题
Kolmogorov生日悖论
The Kolmogorov Birthday Paradox
论文作者
论文摘要
我们证明了生日悖论的Kolmogorov复杂性变体。足够尺寸的字符串随机子集可保证具有两个X和Y的X和Y，具有低k（x/y）。为了证明这一点，我们首先表明有限集成员之间的最小条件kolmogorov如果不是外来的，则它们的最低条件是非常低。外来的集合具有较高的相互信息，并使用停止序列。
We prove a Kolmogorov complexity variant of the birthday paradox. Sufficiently sized random subsets of strings are guaranteed to have two members x and y with low K(x/y). To prove this, we first show that the minimum conditional Kolmogorov complexity between members of finite sets is very low if they are not exotic. Exotic sets have high mutual information with the halting sequence.
