论文标题
算法信息距离的精确表达
Precise Expression for the Algorithmic Information Distance
论文作者
论文摘要
我们认为1998年Bennett，Gács，Li，Vitányi和Zurek引入的两个对象之间的信息距离的概念是从$ y $计算$ x $的程序的最小长度，并从$ x $中计算$ y $。在本文中，已证明距离等于$ \ max（k（x | y），k（y | x））$升至加法对数项，并且猜想这不能将其提高到$ o（1）$ precision。我们在定义中重新审视微妙的问题，并证明了这一猜想。我们表明，如果距离至少在长度上是对数，则此相等性确实具有$ O（1）$相等长度的弦的精度。因此，对于这样的字符串，三角形不等式和表征都具有最佳的精度。最后，我们将结果扩展到设置有限尺寸的$ S $。 We show that for each constant~$s$, the shortest program that prints an $s$-element set $S \subseteq \{0,1\}^n$ given any of its elements, has length at most $\max_{w \in S} K(S|w) + O(1)$, provided this maximum is at least logarithmic in~$n$.
We consider the notion of information distance between two objects $x$ and $y$ introduced by Bennett, Gács, Li, Vitányi, and Zurek in 1998 as the minimal length of a program that computes $x$ from $y$ as well as computing $y$ from $x$. In this paper, it was proven that the distance is equal to $\max (K(x|y),K(y|x))$ up to additive logarithmic terms, and it was conjectured that this could not be improved to $O(1)$ precision. We revisit subtle issues in the definition and prove this conjecture. We show that if the distance is at least logarithmic in the length, then this equality does hold with $O(1)$ precision for strings of equal length. Thus for such strings, both the triangle inequality and the characterization hold with optimal precision. Finally, we extend the result to sets $S$ of bounded size. We show that for each constant~$s$, the shortest program that prints an $s$-element set $S \subseteq \{0,1\}^n$ given any of its elements, has length at most $\max_{w \in S} K(S|w) + O(1)$, provided this maximum is at least logarithmic in~$n$.
