27 Open Problems in Kolmogorov Complexity
27 Open Problems in Kolmogorov Complexity
复制标题
27 柯尔莫哥洛夫复杂度中的开放问题
DOI：
10.1145/3510382.3510389
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Zimand, Marius
中科院分区：
文献类型：
--
作者：
Romashchenko, Andrei;Shen, Alexander;Zimand, Marius
这个公式可以非正式地解读如下：第i条消息mi给我们带来了log(1=pi)“信息位”（无论这意味着什么），并且以频率pi出现，因此H是一条随机消息（随机变量的一个样本）提供的预期信息量。此外，我们可以构造一个最佳的唯一可解码代码，该代码平均每条消息需要大约 H（准确地说，最多 H + 1）位，并且它用大约 log(1=pi) 位对第 i 条消息进行编码，遵循对频繁消息使用短码字的自然想法。这非常适合对上面给出的公式的非正式解读，并且很容易说第 i 条消息“包含 log(1=pi) 位信息”。香农本人屈服于这种诱惑[46，p.11]。 399]当时他撰写了有关熵估计的文章，并将《基础英语》和詹姆斯·乔伊斯的书《芬尼根守灵夜》视为英语文本中高冗余和低冗余的两个极端例子。但是，严格来说，我们只能谈论随机变量的熵，而不能谈论它们的个体值，而“芬尼根守灵夜”不是一个随机变量，只是一个特定的字符串。我们可以定义单个对象的信息量吗？
This formula can be informally read as follows: the ith messagemi brings us log(1=pi) "bits of information" (whatever this means), and appears with frequency pi, so H is the expected amount of information provided by one random message (one sample of the random variable). Moreover, we can construct an optimal uniquely decodable code that requires about H (at most H + 1, to be exact) bits per message on average, and it encodes the ith message by approximately log(1=pi) bits, following the natural idea to use short codewords for frequent messages. This fits well the informal reading of the formula given above, and it is tempting to say that the ith message "contains log(1=pi) bits of information." Shannon himself succumbed to this temptation [46, p. 399] when he wrote about entropy estimates and considers Basic English and James Joyces's book "Finnegan's Wake" as two extreme examples of high and low redundancy in English texts. But, strictly speaking, one can speak only of entropies of random variables, not of their individual values, and "Finnegan's Wake" is not a random variable, just a specific string. Can we define the amount of information in individual objects?
登录
查看更多内容
影响因子：
0.5
作者：
L. Bienvenu;P. Gács;M. Hoyrup;Cristobal Rojas;A. Shen
通讯作者：
A. Shen
柯尔莫哥洛夫复杂性和密码学
DOI：
--
发表时间：
2011
期刊：
arXiv.org
影响因子：
--
作者：
A. Muchnik
通讯作者：
A. Muchnik
分层可计算性和图像随机性
影响因子：
0.5
作者：
L. Bienvenu;M. Hoyrup;A. Shen
通讯作者：
A. Shen
短程序的线性列表逼近（或几个随机位的幂）
DOI：
--
发表时间：
2013
期刊：
Cybersecurity and Cyberforensics Conference
影响因子：
--
作者：
Bruno Bauwens;Marius Zimand
通讯作者：
Marius Zimand
二进制串的上半格，其关系为“x 是 y 的简单条件”
DOI：
--
发表时间：
1999
期刊：
Proceedings. Fourteenth Annual IEEE Conference on Computational Complexity (Formerly: Structure in Complexity Theory Conference) (Cat.No.99CB36317)
影响因子：
--
作者：
A. Muchnik;Andrei E. Romashchenko;A. Shen;N. Vereshchagin
通讯作者：
N. Vereshchagin