论文标题
空间有空间的Kolmogorov复杂性的不平等
Inequalities for space-bounded Kolmogorov complexity
论文作者
论文摘要
香农信息理论与算法信息理论之间存在平行性。特别是，对于随机变量和琴弦的kolmogorov元素的香农熵而言，线性不平等也是如此（Hammer等，1997），以及集合的大小和集合的大小（Chan，Yeung，Yeung，Yeung，Romashchenko，Shen，Shen，vereshchagin，1998年）。这种并行性始于Kolmogorov-Levin公式（1968），其对数精度的弦对的复杂性。 Longpré（1986）证明了该公式的一个版本，以实现太空结合的复杂性。 在本文中，使用Sipser's Trick（1980），我们证明了Longpré的结果的改进版本。然后，使用此空间结合，我们表明，对于由空间结合的kolmogorov复杂性，在头顶上有多项式空间的kolmogorov复杂性也是如此。
There is a parallelism between Shannon information theory and algorithmic information theory. In particular, the same linear inequalities are true for Shannon entropies of tuples of random variables and Kolmogorov complexities of tuples of strings (Hammer et al., 1997), as well as for sizes of subgroups and projections of sets (Chan, Yeung, Romashchenko, Shen, Vereshchagin, 1998--2002). This parallelism started with the Kolmogorov-Levin formula (1968) for the complexity of pairs of strings with logarithmic precision. Longpré (1986) proved a version of this formula for space-bounded complexities. In this paper we prove an improved version of Longpré's result with a tighter space bound, using Sipser's trick (1980). Then, using this space bound, we show that every linear inequality that is true for complexities or entropies, is also true for space-bounded Kolmogorov complexities with a polynomial space overhead.
