柯尔莫哥洛夫复杂性

伟大的数学家柯尔莫哥洛夫于1965年提出了对象固有描述复杂性的定义，标志着他毕生致力于数学、复杂性和信息论的研究。迄今为止，我们讨论的对象X是根据概率质量函数p(x)抽取的随机变量。如果X是随机的，那么事件X = x的描述复杂性在某种意义上是\(\text{log}\frac{1}{p(x)}\)，因为⌈\(\text{log}\frac{1}{p(x)}\)⌉是用香农码描述x所需的位数。人们立即注意到，此类对象的描述复杂性取决于概率分布。

柯尔莫哥洛夫更进一步。他将一个对象的算法（描述）复杂度定义为描述该对象的最短二进制计算机程序的长度。（显然，计算机，作为最通用的数据解压器，将在有限的计算量之后使用此描述来展示所描述的对象。）因此，一个对象的柯尔莫哥洛夫复杂度无需考虑概率分布。柯尔莫哥洛夫做出了至关重要的观察：复杂性的定义本质上与计算机无关。一个令人惊奇的事实是，随机变量的最短二进制计算机描述的预期长度近似等于其熵。因此，最短计算机描述充当一个通用代码，对所有概率分布都一致有效。从这个意义上讲，算法复杂度是熵的概念先驱。

或许，将柯尔莫哥洛夫复杂度视为一种思考方式，是理解本章作用的一个好视角。实践中，人们不会使用最短的计算机程序，因为找到这样一个最小程序可能需要无限长的时间。但实践中，人们可以使用非常短的、不一定是最小的程序；而寻找这种短程序的想法可以引出通用代码、归纳推理的良好基础、奥卡姆剃刀原则（“最简单的解释是最好的”）的形式化，以及对物理学、计算机科学和通信理论的根本理解。