XiaoMi-AI文件搜索系统
World File Search System编码定理
扩展编码定理及其在量子复杂性中的应用
Kolmogorov 复杂度的研究起源于 [Kolmogorov 1965] 的工作。[Levin 1974] 和 [Chaitin 1975] 引入了 Kolmogorov 复杂度的规范自界定形式。[Solomonoffi1964] 引入了通用概率 m。有关本文中使用的概念的历史的更多信息，请参阅教科书 [Li and Vit´anyi 2008]。本文的主要定理是一个不等式，它具有字符串与停机序列的互信息。有关该术语的更多背景知识，请参阅 [Vereshchagin and Vit´anyi 2004b]。引理 4.1 使用了随机性的概念。如果字符串是简单概率分布的典型，则它是随机的。[Shen 1983, 1999; V'Yugin 1987]。随机性是算法统计的一个研究领域，可以在[Vereshchagin and Vit´anyi 2004a；Vereshchagin and Vit´anyi 2010；Vereshchagin 2013；Vereshchagin and Shen 2016]中找到。
最佳编码定理在时间遇到的Kolmogorov复杂性
kolmogorov复杂性中的经典编码定理指出，如果n-bit string x用概率δ通过具有无前域域的算法进行采样，则k（x）≤log（1 /δ） + o（1）。在最近的一项工作中，Lu和Oliveira [31]建立了该结果的无条件时间限制的版本，表明如果X可以有效地采样概率Δ，则RKT（X）= O（log（1 /δ） + O（log o（log n），RKT表示RKT的随机模拟Levin kt的复杂度的随机模拟。不幸的是，当将经典编码定理的应用传输到时键设置时，该结果通常不足，因为它实现了o（log（1 /δ））结合的o（log（1 /δ）），而不是信息理论的最佳log（1 /δ）。是出于这种差异的激励，我们研究了在时间限制的设置中的最佳编码定理。我们的主要贡献可以总结如下。
