《夸克与美洲豹》第七节

计算复杂性关注问题规模趋于无穷时求解时间的变化，与日常所说的“复杂”含义不同；后者更关心描述系统性质需要多长的信息。

计算复杂性关注问题规模趋于无穷时求解时间的变化，与日常所说的“复杂”含义不同；后者更关心描述系统性质需要多长的信息。以生态系统为例，衡量热带森林与温带森林的复杂程度，取决于数物种、数相互作用等描述的长短，而描述总要在某一精细度上停止，物理学家称之为“粗粒化”。

为使复杂性可比较，需先规定细节层次。以N个人的通信网络为例，把人画成点、允许的通信用无向连线表示，得到无向图。在8个点的情形下，全无连线的A模式与全连线的F模式其实同样简单，因为两者的描述等长；互补的模式复杂性也近乎相同。相比之下，部分连线的模式更复杂，而C、D哪种更复杂则取决于所用语言。

由此看来，复杂性依赖于描述者与背景，并非事物的固有属性。描述长度还受语言和双方共享知识的影响，且应以事先公认的术语、通过通信传递、并取可能的最短表述为准。