熵和复杂度

看到 b 站一堆完全没学过信息论和计算复杂度的在争论化学的熵（entropy），信息论的信息熵（Shannon Entropy），信息复杂度（Kolmogov Complexity），计算复杂度（Computational Complexity）的区别。。。为什么有人敢不先自己了解一下（看看教科书，问问 AI）就直接在网上公开的“我认为xxx”，“我觉得xxx”。

核心概念定义

信息熵 (Shannon Entropy) —— 统计的平均值

• 提出者： 香农 (Claude Shannon), 1948。
• 对象： 一个概率分布或随机变量（产生数据的源头），而不是某一条具体的消息。
• 定义： 表示从一个概率分布中产生一个事件所带来的平均不确定性。
• 直观理解： 如果我从这个源头不断获取数据，平均每个符号需要多少个比特来编码？
• 例子： 投掷一枚均匀硬币，正面反面概率各 50%。无论你扔出什么结果，这个过程的熵是 1 bit。

信息复杂度 (Kolmogorov Complexity) —— 个体的描述长度

• 提出者： 柯尔莫哥洛夫 (Andrey Kolmogorov), 1960s。
• 对象： 一个特定的字符串或具体的对象（已经产生的数据）。
• 定义： 在通用的图灵机上，能输出该字符串的最短程序的长度。
• 直观理解： 如果我想把这个文件压缩到极致，它最少能被压缩成多大？
• 例子：
  • 字符串 00000000...（一万个0）：复杂度很低，程序只需写 print("0" * 10000)。
  • 字符串 84920184...（一万个随机数）：复杂度很高，程序可能不得不写 print("84920184...")，即把整个串硬编码进去。

维度	信息熵 (Entropy)	柯尔莫哥洛夫复杂度 (Complexity)
视角	预期的/统计的。关注产生数据的“源头”。	个体的/描述的。关注数据“本身”。
依赖性	依赖于概率分布。需要知道数据出现的概率。	不依赖概率，只依赖于对象本身的结构。
可计算性	可计算（只要知道概率分布）。	不可计算（受停机问题限制，你永远无法证明你找到了最短的程序）。
圆周率 \(\pi\)	\(\pi\) 的数字分布看起来是随机的，视为随机源时熵很高。	\(\pi\) 可以由很短的代码生成，因此复杂度很低。
本质	衡量不确定性 (Uncertainty)。	衡量随机性 (Randomness) 或结构性。

信息熵和化学的熵的关系

香农发明信息熵这个概念肯定借鉴了科学里 entropy 熵这个概念。狭义的定义是系统的混乱程度。但换个角度想，可以看作是系统的“多样性”或“不确定性”。这与香农构想的信息熵定义一致。

信息熵和信息复杂度的关系

我目前发现的唯一的关系是：

低信息熵 implies 低信息复杂度

考虑两者的定义。信息复杂度可以看作是表示内容的最少bit，换句话说，如果内容可以用少量bit来表示，那么信息复杂度就低。于是，因低信息熵的内容往往可以很简单的进行表示（不然implies不确定性过高，冲突了），这implies内容可以用少量bit表示，也就是，信息复杂度很低。

但其他蕴含implies关系都可以通过反例证伪。

考虑 \(\pi\)，信息熵十分高（无穷个小数位，数字分布十分无规律），但可以通过很短几行代码通过无限迭代来表示（一个永远递归的程序）。这表示了低信息复杂度不等于低信息熵，也就是， 存在很少数量的bit可以表示趋于负无穷的信息熵的内容。

高xxx可以通过contrapositive得到（高信息复杂度implies高信息熵，反之可以通过 \(\pi\) 证伪）。

信息复杂度和计算复杂度的关系

可以说对应了程序的存储占用和运行时间（也就是空间复杂度和时间复杂度）。如上面所说，一个计算 \(\pi\) 的程序源代码并不复杂，但是时间是无穷的（不停机）。

换个角度来想，对于一个内容，降低程序的储存占用（如压缩文件）往往代表了想要提取这个内容原本的样子需要的时间就会增加（需要解压缩）。

但信息熵并不对应（等价于）信息复杂度和计算复杂度加在一起的复杂度。考虑 “第 100 亿个质数”，由于是确定的，信息熵为0；但信息复杂度和计算复杂度都十分高。