本学渣刚进积水潭师专时曾经很喜欢系统科学……
以下基本就是我所知的关于复杂性的各种絮叨，有误请轻拍砖
参考文献列表稍后附上
我们一般都对物理系统的复杂程度有着直观的认识，例如：人类的大脑比食盐晶体要复杂得多。同时也有着一些关于系统复杂度的推测，例如：充分高的复杂度才能孕育生命和智能。复杂性通常产生于完全有序和完全无序间的过渡带。等等。然而，为了以严谨的方式刻画物理复杂性的一般规律，特别是为了研究统计物理的重要课题“自组织”现象，我们需要一个量化系统有效结构丰富程度的参量。
这个符合我们要求的量应该至少满足以下两点要求：
1， 仅量化有效结构的复杂程度。有效结构意指被我们认为是携带着有意义的模式的结构，无意义的随机结构不应该计入，因此这个量对具有过于简单的周期序的系统（完美单晶）和完全被随机性规律支配的系统（理想气体）都应该取低。显然这两类系统对我们而言都属于“简单”的，并且不吸引复杂系统研究者的兴趣。
2， 缓增律（Slow GrowthLaw）。这个量的增长率应该有一个合理的上界。直观来看，这代表着形成复杂的结构需要不可约减的历史积累。设想如果总是存在用时足够短的过程，令寻常的碎磨砂玻璃突然具备相当于人类DNA的复杂度，这也是显得很奇怪的。
根据这两点认识，Charles Bennett考察了以下具有作为复杂度候选资格的常见概念（包括他自己提出的一个原创概念）：
【熵】：这是最容易被想到的概念，也是对复杂性科学具有很强历史意义的一个概念。然则它并不符合上述的两点要求。从第一点来看，活人脑的熵密度是介于均匀高温气体和低温单晶之间的，而后两者都没什么有效结构。显然，平衡态的熵值最大化，很大程度上来自于体系中高度无序，而非有效结构的贡献。从第二点来看，熵的增长率一般并没有上界，并且高的增长率也不必然反映复杂性的迅速增加（例如爆炸）。
鉴于同样的原因，熵以外的其他热力学势也是不适合的。这包括薛定谔所用的所谓“负熵”概念（薛定谔本人承认引入这概念只是为了通俗解释自由能）。
【描述复杂度】：一种比较符合直觉的途径是用完整描述系统所需的信息量来代表这个系统的复杂度。不少离散系统的动力学行为可以被适当的计算模型（通常是2维或3维元胞自动机）所有效模拟（铁磁相变等），在给定的通用计算设备上实现这一模拟所用的最短程序长度即可以定义为该体系的信息量，通称Kolmogorov复杂度。当然，这种复杂度会依赖于计算设备，但由于通用计算设备可以相互模拟，所产生的差别对于信息量较大的情形无关紧要。
选定了合适的参考机，Kolmogorov复杂度本质上只依赖于对象本身的结构，不依赖于概率分布，从而允许我们绕过系综理论去谈论单个微观态的信息量。W.H.Zurek利用这点将其应用于解决Maxwell妖佯谬。推广到量子态的Kolmogorov复杂度可被应用于量子通信和量子计算领域。虽然有这些特性，这种复杂度的缺陷却和熵几乎一样：完全随机的结构不存在任何可以用来简化描述的规律，因此描述反而是最冗长的，具备最高的复杂度，但这并不反映有效结构的存在。而且，描述复杂度是空间复杂度性质的度量，没有依据证明其满足缓增律，不过，这也给出了提示：更好地反映复杂性的度量似乎应该从时间复杂度上着手，这点引出了逻辑深度的定义。
Leonid Levin的优美定理表明，熵和描述复杂度其实可以粗略地看作是分别从概率角度和算法角度对同一个概念的度量（这里的熵兼指热力学熵和完整描述的香农熵二者）。然而恰因如此，两者都缺乏区分有意义的信息（硬盘存储的数据，DNA中编码的遗传信息等）和随机性的能力，需要我们人工地对有效信息和噪声做出分离，但这就与我们的初衷相违背。这结果也提醒我们不能将信息量直接等同于直觉中的“复杂性”概念。
Murray Gell-Mann在圣塔菲研究所期间提出的有效复杂度（effectivecomplexity）概念则是试图结合熵和描述复杂度两者进行互补，将量度随机性的部分从信息量中扣除来获得描述有效结构的信息量。
【互信息和关联长度】：使用这类度量作为标准的思路是：一个产生复杂现象的系统应该是各部分间存在强烈关联的有机整体，长距离上的（统计）关联应该是复杂性的关键特征。
基于长程序的参量在刻画一大类临界现象中的复杂性方面取得了相当的成功，这表明它们确实抓住了复杂系统的某些共通性质。不过，一定量的互信息可能显示了有序组织的存在，但互信息的高低却不一定对应着结构意义上的复杂程度。理想单晶并不因为包含着长程序而显著地比单个元胞复杂。另外，难以证明这类参量满足适当形式的“缓增律”。粗略来讲，它们的快速增长至少在原理上可以被单纯的信息复制和传播过程实现，但这不代表原体系复杂性也因之迅速增加。因此，它们最好被看做是常见于宏观复杂性的生成过程中的副产品，而非复杂性本身的度量（它们伴随复杂性出现的特性依然是很有研究价值的问题）。
【自相似性相关参量】：所有基于系统的无标度特征/分形特征的参量都可以归为此类。例如：分形维数。它们同样能够在一定程度上反映出复杂系统中的常见特征，不过，并非所有的有效结构都含有自相似性。把【互信息与关联长度】作为复杂性度量的局限性也同样适用于这类参量。
【逻辑深度】：Bennett创造的这一概念和Kolmogorov复杂度一样，最初是定义为二元数据串的属性。要将它用于物理学，需要给系统状态适当的编码，使得编码的复杂性恰能反映出系统状态的复杂性，这一般可以像Kolmogorov复杂度的应用一样指定合适的通用机，将模拟对象的程序视作对象的编码来解决。如果说Kolmogorov复杂度能理解为数据的最小压缩包的规模，逻辑深度（Logical depth）则对应着最小压缩包的解压时间。数学理论的高度复杂性来自于从其最简表达（一组独立的公理）还原出理论整体所需要的大量推理步骤，逻辑深度刻画的正是这种特征。
由于任意有限二元串都至少存在一个直接逐字输出其本身的平庸程序，它的运行时间只是线性时间。因此，逻辑深度随着串长度线性增长的数据可以被作为逻辑浅的代表。容易看出，不存在简化描述的随机长串（Kolmogorov复杂度最大化）通常是逻辑浅的，因为其最简生成器就是平庸程序。相反地，具有简单周期序的长串如01010101……也是逻辑浅的，尽管它们的最简生成器不是平庸程序，但其算法过于简单以致于只需要线性时间。逻辑深的串必须具有更加复杂的规律，使得最简生成算法需要超过线性时间的准备。作为数据的属性，逻辑深度确实能符合我们的第一条要求，但将它用在物理系统上时是否也必然有同样的有效性则是一个猜想，至少对于部分可以被元胞自动机建模的体系是成功的，此时编码长度近似正比于系统的自由度。
将逻辑深度用于物理描述的最强动机来自于它满足缓增律，无论系统的动力学机制具有确定性的还是概率性的特征。设想我们用投N次均匀硬币的方式生成一个长度为N的二元程序，则该程序接受串x作为输入，运行t步后产生的输出y的逻辑深度相对x的增长超过t的概率恒不超过。此处的常数c只依赖于定义深度所用的通用图灵机，不依赖于N和x（它们可以是任意的）。我们通常会假定系统起源于某个均匀各向同性的初态，过高的对称性将会导致初态具有很浅的逻辑深度。因此，逻辑深度反映的是从“自然的”初态演化到当前状态的最小历史。当然，刻意选择稀有的程序可以让逻辑深度更快地增长，但这种刻意选择的能力本身就反映了某些复杂的筛选过程的存在。观察到逻辑深度过高的对象有两种可能：1，它经历了漫长的，非平凡的自然演化过程。2，它来自于某个高智能体人工的设计。两者都代表了可能引起研究者兴趣的内容。
逻辑深度作为时间复杂度类型的概念也有其缺陷。在不同的计算设备上逻辑深度至多只能确定到多项式关系以内，例如：在通用机U1上深度为D的态，在U2上深度也许会变成。因此，逻辑深度相对于可以确定到常数差以内的Kolmogorov复杂度更依赖于标准计算模型的选择。一种克服该缺陷的途径是考虑逻辑深度的对数在取热力学极限情况下的增长趋势而非逻辑深度本身。另一种是根据物理系统本身的特性确定计算模型，Bennett的原始定义中用的是传统的通用图灵机。David Deustch认为所有的有限系统实质上都能视作量子计算机，因此提议用量子计算模型定义的变体“量子深度”（Q-depth）作为标准，系统复杂性增长的趋势应该用量子深度的增长而非熵的增长来表征。J.Machta则认为用图灵机这样的串行计算模型进行定义会导致逻辑深度过度地依赖于系统的规模，因此选用并行随机存储器（PRAM）作为标准定义了变体“并行深度”（Parallel depth），并行深度的特点是简单地将原系统进行复制几乎不改变其深度，多个独立子系统组合成的系统深度完全取决于子系统中深度最高者，从而更多地反映了结构意义上的复杂性。并行深度已确认可被应用于研究扩散限制集聚（DLA），自旋玻璃等物理体系。
基于算法的度量或多或少需要假定物理对象类似于数字计算设备，为了获得更适用于物理体系的参量，Seth Lloyd利用描述复杂度和熵的对应关系定义了逻辑深度的对应：热力学深度。热力学深度只需要应用传统的统计物理学概念就可以定义，免去了给微观态一个人工编码的主观任意性，Gell-Mann则发现有效复杂度概念与热力学深度间也存在着对应关系，这也暗示着所谓“有效的”复杂性确实是可以得到较为客观的量化的。
以下基本就是我所知的关于复杂性的各种絮叨，有误请轻拍砖
参考文献列表稍后附上
我们一般都对物理系统的复杂程度有着直观的认识，例如：人类的大脑比食盐晶体要复杂得多。同时也有着一些关于系统复杂度的推测，例如：充分高的复杂度才能孕育生命和智能。复杂性通常产生于完全有序和完全无序间的过渡带。等等。然而，为了以严谨的方式刻画物理复杂性的一般规律，特别是为了研究统计物理的重要课题“自组织”现象，我们需要一个量化系统有效结构丰富程度的参量。
这个符合我们要求的量应该至少满足以下两点要求：
1， 仅量化有效结构的复杂程度。有效结构意指被我们认为是携带着有意义的模式的结构，无意义的随机结构不应该计入，因此这个量对具有过于简单的周期序的系统（完美单晶）和完全被随机性规律支配的系统（理想气体）都应该取低。显然这两类系统对我们而言都属于“简单”的，并且不吸引复杂系统研究者的兴趣。
2， 缓增律（Slow GrowthLaw）。这个量的增长率应该有一个合理的上界。直观来看，这代表着形成复杂的结构需要不可约减的历史积累。设想如果总是存在用时足够短的过程，令寻常的碎磨砂玻璃突然具备相当于人类DNA的复杂度，这也是显得很奇怪的。
根据这两点认识，Charles Bennett考察了以下具有作为复杂度候选资格的常见概念（包括他自己提出的一个原创概念）：
【熵】：这是最容易被想到的概念，也是对复杂性科学具有很强历史意义的一个概念。然则它并不符合上述的两点要求。从第一点来看，活人脑的熵密度是介于均匀高温气体和低温单晶之间的，而后两者都没什么有效结构。显然，平衡态的熵值最大化，很大程度上来自于体系中高度无序，而非有效结构的贡献。从第二点来看，熵的增长率一般并没有上界，并且高的增长率也不必然反映复杂性的迅速增加（例如爆炸）。
鉴于同样的原因，熵以外的其他热力学势也是不适合的。这包括薛定谔所用的所谓“负熵”概念（薛定谔本人承认引入这概念只是为了通俗解释自由能）。
【描述复杂度】：一种比较符合直觉的途径是用完整描述系统所需的信息量来代表这个系统的复杂度。不少离散系统的动力学行为可以被适当的计算模型（通常是2维或3维元胞自动机）所有效模拟（铁磁相变等），在给定的通用计算设备上实现这一模拟所用的最短程序长度即可以定义为该体系的信息量，通称Kolmogorov复杂度。当然，这种复杂度会依赖于计算设备，但由于通用计算设备可以相互模拟，所产生的差别对于信息量较大的情形无关紧要。
选定了合适的参考机，Kolmogorov复杂度本质上只依赖于对象本身的结构，不依赖于概率分布，从而允许我们绕过系综理论去谈论单个微观态的信息量。W.H.Zurek利用这点将其应用于解决Maxwell妖佯谬。推广到量子态的Kolmogorov复杂度可被应用于量子通信和量子计算领域。虽然有这些特性，这种复杂度的缺陷却和熵几乎一样：完全随机的结构不存在任何可以用来简化描述的规律，因此描述反而是最冗长的，具备最高的复杂度，但这并不反映有效结构的存在。而且，描述复杂度是空间复杂度性质的度量，没有依据证明其满足缓增律，不过，这也给出了提示：更好地反映复杂性的度量似乎应该从时间复杂度上着手，这点引出了逻辑深度的定义。
Leonid Levin的优美定理表明，熵和描述复杂度其实可以粗略地看作是分别从概率角度和算法角度对同一个概念的度量（这里的熵兼指热力学熵和完整描述的香农熵二者）。然而恰因如此，两者都缺乏区分有意义的信息（硬盘存储的数据，DNA中编码的遗传信息等）和随机性的能力，需要我们人工地对有效信息和噪声做出分离，但这就与我们的初衷相违背。这结果也提醒我们不能将信息量直接等同于直觉中的“复杂性”概念。
Murray Gell-Mann在圣塔菲研究所期间提出的有效复杂度（effectivecomplexity）概念则是试图结合熵和描述复杂度两者进行互补，将量度随机性的部分从信息量中扣除来获得描述有效结构的信息量。
【互信息和关联长度】：使用这类度量作为标准的思路是：一个产生复杂现象的系统应该是各部分间存在强烈关联的有机整体，长距离上的（统计）关联应该是复杂性的关键特征。
基于长程序的参量在刻画一大类临界现象中的复杂性方面取得了相当的成功，这表明它们确实抓住了复杂系统的某些共通性质。不过，一定量的互信息可能显示了有序组织的存在，但互信息的高低却不一定对应着结构意义上的复杂程度。理想单晶并不因为包含着长程序而显著地比单个元胞复杂。另外，难以证明这类参量满足适当形式的“缓增律”。粗略来讲，它们的快速增长至少在原理上可以被单纯的信息复制和传播过程实现，但这不代表原体系复杂性也因之迅速增加。因此，它们最好被看做是常见于宏观复杂性的生成过程中的副产品，而非复杂性本身的度量（它们伴随复杂性出现的特性依然是很有研究价值的问题）。
【自相似性相关参量】：所有基于系统的无标度特征/分形特征的参量都可以归为此类。例如：分形维数。它们同样能够在一定程度上反映出复杂系统中的常见特征，不过，并非所有的有效结构都含有自相似性。把【互信息与关联长度】作为复杂性度量的局限性也同样适用于这类参量。
【逻辑深度】：Bennett创造的这一概念和Kolmogorov复杂度一样，最初是定义为二元数据串的属性。要将它用于物理学，需要给系统状态适当的编码，使得编码的复杂性恰能反映出系统状态的复杂性，这一般可以像Kolmogorov复杂度的应用一样指定合适的通用机，将模拟对象的程序视作对象的编码来解决。如果说Kolmogorov复杂度能理解为数据的最小压缩包的规模，逻辑深度（Logical depth）则对应着最小压缩包的解压时间。数学理论的高度复杂性来自于从其最简表达（一组独立的公理）还原出理论整体所需要的大量推理步骤，逻辑深度刻画的正是这种特征。
由于任意有限二元串都至少存在一个直接逐字输出其本身的平庸程序，它的运行时间只是线性时间。因此，逻辑深度随着串长度线性增长的数据可以被作为逻辑浅的代表。容易看出，不存在简化描述的随机长串（Kolmogorov复杂度最大化）通常是逻辑浅的，因为其最简生成器就是平庸程序。相反地，具有简单周期序的长串如01010101……也是逻辑浅的，尽管它们的最简生成器不是平庸程序，但其算法过于简单以致于只需要线性时间。逻辑深的串必须具有更加复杂的规律，使得最简生成算法需要超过线性时间的准备。作为数据的属性，逻辑深度确实能符合我们的第一条要求，但将它用在物理系统上时是否也必然有同样的有效性则是一个猜想，至少对于部分可以被元胞自动机建模的体系是成功的，此时编码长度近似正比于系统的自由度。
将逻辑深度用于物理描述的最强动机来自于它满足缓增律，无论系统的动力学机制具有确定性的还是概率性的特征。设想我们用投N次均匀硬币的方式生成一个长度为N的二元程序，则该程序接受串x作为输入，运行t步后产生的输出y的逻辑深度相对x的增长超过t的概率恒不超过。此处的常数c只依赖于定义深度所用的通用图灵机，不依赖于N和x（它们可以是任意的）。我们通常会假定系统起源于某个均匀各向同性的初态，过高的对称性将会导致初态具有很浅的逻辑深度。因此，逻辑深度反映的是从“自然的”初态演化到当前状态的最小历史。当然，刻意选择稀有的程序可以让逻辑深度更快地增长，但这种刻意选择的能力本身就反映了某些复杂的筛选过程的存在。观察到逻辑深度过高的对象有两种可能：1，它经历了漫长的，非平凡的自然演化过程。2，它来自于某个高智能体人工的设计。两者都代表了可能引起研究者兴趣的内容。
逻辑深度作为时间复杂度类型的概念也有其缺陷。在不同的计算设备上逻辑深度至多只能确定到多项式关系以内，例如：在通用机U1上深度为D的态，在U2上深度也许会变成。因此，逻辑深度相对于可以确定到常数差以内的Kolmogorov复杂度更依赖于标准计算模型的选择。一种克服该缺陷的途径是考虑逻辑深度的对数在取热力学极限情况下的增长趋势而非逻辑深度本身。另一种是根据物理系统本身的特性确定计算模型，Bennett的原始定义中用的是传统的通用图灵机。David Deustch认为所有的有限系统实质上都能视作量子计算机，因此提议用量子计算模型定义的变体“量子深度”（Q-depth）作为标准，系统复杂性增长的趋势应该用量子深度的增长而非熵的增长来表征。J.Machta则认为用图灵机这样的串行计算模型进行定义会导致逻辑深度过度地依赖于系统的规模，因此选用并行随机存储器（PRAM）作为标准定义了变体“并行深度”（Parallel depth），并行深度的特点是简单地将原系统进行复制几乎不改变其深度，多个独立子系统组合成的系统深度完全取决于子系统中深度最高者，从而更多地反映了结构意义上的复杂性。并行深度已确认可被应用于研究扩散限制集聚（DLA），自旋玻璃等物理体系。
基于算法的度量或多或少需要假定物理对象类似于数字计算设备，为了获得更适用于物理体系的参量，Seth Lloyd利用描述复杂度和熵的对应关系定义了逻辑深度的对应：热力学深度。热力学深度只需要应用传统的统计物理学概念就可以定义，免去了给微观态一个人工编码的主观任意性，Gell-Mann则发现有效复杂度概念与热力学深度间也存在着对应关系，这也暗示着所谓“有效的”复杂性确实是可以得到较为客观的量化的。
其实我看不懂啦
