【内容提要】本文通过对历史上复杂性与随机性关系的认识回顾，展示和分析了起源于计算机科学领域的kolmogorov复杂性与随机性的直接关联，分析了盖尔曼的有效复杂性概念，论证了两种复杂性与随机性的关系，以及随机性的不同情况，力图剥离混合在复杂性与随机性相互关系上的一些误读和误解，还复杂性与随机性一种客观的本真关系。
【关键词】复杂性/计算复杂性/算法复杂性/随机性/有效复杂性ⅰ/有效复杂性ⅱ

【正文】
最近，我们在研究复杂性问题的过程中，发现复杂性与随机性的关系具有特别的意义，许多国内外的学者在复杂性与随机性的关系认识上，常常以随机性代替复杂性，认为随机性就是复杂性的内容之一。本文力图剥离混合在复杂性与随机性相互关系上的一些误读和误解，还复杂性与随机性一种客观的本真关系。
　　一、历史上复杂性与随机性的认识回顾
科学上经典的复杂性的概念，最早起源于计算机科学研究领域，当然它主要参考了物理学当时的基本观念。
　　（一）建基随机性上的两种复杂性概念
为了探索复杂性与随机性的关系，我们先了解计算复杂性、算法复杂性的概念。
首先让我们从信息理论的角度来看待问题。信息的简单还是复杂涉及的是表达信息的序列串如何。简单的非复杂系统的产生指令很简短，通常也很明显：例如，所有项相加即为和。这样复杂性可以操作性地定义为：寻找最小的程序或指令集来描述给定“结构”——一个数字序列。这个微型程序的大小相关于序列的大小就是其复杂性的测量。
序列111111…是均匀的（不复杂的）。WWW.11665.COM对应的程序如下；在每一个1后续写1。这个短程序使得这个序列得以延续，不管要多长都可以办到。
序列110110110110…的复杂性高一些，但仍然很容易写出程序：在两个1后续写0并重复。甚至序列110110100110110100…也可以用很短的程序来描述；在两个1后续写0并重复；每三次重复将第二个1代之以0。这样的序列具有可定义的结构，有对应的程序来传达信息。比较这三个一个比一个复杂些的序列。再看下面的序列11010010110111010010…，它不再是一个可识别的结构，若想编程必须将它全部列出。但是如果它是完全随机性的，那么，我们根据概率规则，可以知道最终在这个数串中0和1的出现几乎是等概率的。
于是为了解决这些关于如何认识复杂性增长和判别复杂性程序的问题，科学家们定义了多种描述性的复杂性概念。
计算复杂性(computational complexity)源于20世纪30年代数学逻辑发展过程中提出的一些深刻命题。它们都有自己特定的问题规模n，计算复杂性就是指解决问题随问题规模n增长而需要的代价增长。这种简单性和复杂性的分野是，如果计算时间（或空间）的增长不超过n的某个幂次或多项式，那么该问题是简单的，称为p类问题。如果增长速率超过n的任何多项式，则问题是困难的，称为np类（np即“非确定多项式”non-deterministic polynomial的缩写）问题，即复杂性问题之一。如推销商的路线选择问题（travelling selesman problem，简称tsp）就属于问题中的“完全np”一类问题。此类问题的特点是，随着问题涉及面增加，其计算量将指数性或失控式地增长。
对计算复杂性的常见度量是时间和空间。一般地说，所谓时间就是一个计算中离散步骤的数目；空间就是指计算指令读取独特的存储地址的数目。[1]如前所述，时间上的计算复杂性即一个计算机描述一个系统（或解一个问题）所需要的时间；空间上的计算复杂性即描述一个系统所需要的计算机存储量。
算法复杂性(algorithmic complexity)，主要是由a.n.kolmogorov,[2]g.j.chaitin[3]和r.j.solomonoff[4]在20世纪60年代中期分别独立提出的概念，又称为kolmogorov复杂性。基本思想和定义如下：
对每一个d域中的对象x，我们称最小程序p的长度丨p丨就是运用指定方法s产生的关于对象x的复杂性。对计算机s而言，设给定的符号串为x，将产生x的程序记为p。对一个计算机来说，x是输入，p是输出。粗略的说，关于一个符号串x的kolmogorov复杂性，就是产生x的最短程序p的长度。上述定义可写为：[5]



k[,s](x)=min｛丨p丨:s(p)=n(x)｝
k[,s](x)=∞　如果不存在p.



其中k[,s](x)即kolmogorov复杂性。后一个公式的含义是明显的，即如果传送的符号串完全杂乱无章，找不到任何规律（即程序p），那么，复杂性就等于符号串本身，而符合串是无规无穷数，复杂性即无穷。因此在算法复杂性中，实际上是越随机性(random)的东西，越不可认识，其结果是它越复杂。换句话说，复杂的随机性对象有最大的复杂性，因为不可能压缩对其对象的描述。[6]
　　（二）kolmogorov复杂性的影响和有效复杂性的提出
kolmogorov复杂性定义实际上支配了后来计算机科学上对复杂性的几乎所有的研究，以后又波及到几乎所有科学领域。例如，f.cramer就是按照这种思路把复杂性程度分为三个等级：亚复杂性、临界复杂性和根本复杂性。所谓亚临界复杂性是指系统表面复杂但其实很简单，或许是算术性的。简单的物理定律，如牛顿定律可以用于得到的决定性系统；所谓临界复杂性是指在复杂性的特定阶段——在它的临界值上——开始出现某些结构。最简单的情况是对流和对流图案形式。这个复杂度称为临界复杂性。这些系统构成一些亚系统，例如进化系统或不可逆热力学系统；所谓根本复杂性是指“只要系统有着不确定性解或混沌解它就是根本复杂的”，[7]“一旦程序的大小变得与试图描述的系统可以相提并论，不能再对系统进行编程。当结构不可辨识时——即当描述它的最小算法具有的信息比特数可与系统本身进行比较时——我称之为根本复杂性。根本复杂性的这个定义是以a.n.kolomogorov(1965)的方程为基础的。”([7],p.211)
按照f.cramer的认识，根本复杂性相当于无法认识。根本复杂性即那些表现得完全随机性（random或stochastic）、描述结果与被描述对象可以相提并论，完全无法获得规律性认识，简单地说，无法辨识即根本复杂性。
所以，根本复杂性＝完全随机性。
f.cramer还按照复杂性程序的不同，比较了数学、一般科学理论、物理学、生物学、进化过程、科学之外系统（包括科学作为一个整体系统、哲学、美学、语言、宗教和历史）等6类知识体系的描述复杂性情况，按照他的分类，我们看到几乎每一个认识体系都有自己的三类复杂性（第一类实际上是简单性）情况。
当然，这种通过图灵机方式，用算法耗用资源的方法表示计算复杂性程序，给研究的难度做了一个很好的客观的划界。但是，如果一个对象根本无法简约对对象的描述，其描述长度与构成对象的组分“程序”完全一样，甚至完全不存在一个最短描述程序p，算法复杂性给出的复杂性定义与我们在物理学等科学上对随机性的复杂性认识就有所背离。
例如，完全随机性的全同粒子组成的气体系统，它的内部状态是无法给出程序描述的随机状态，但是它的结果却是非常简单的、确定的，不具有复杂性特征。
因此，反对复杂性等于随机性的观点也是应该考虑的。其典型的代表是盖尔曼，他提出“有效复杂性”概念。所谓“有效复杂性，大致可以用对该系统或数串的规律性的简要描述长度来表示”。([8],p.49)他认为算法复杂性不能用来定义复杂性，其原因在于算法复杂性具有不可计算性和随机性。他的根本观点是随机性不是复杂性，即有效复杂性这一概念的作用，尤其当它不是内部有效复杂性时，与进行观察的复杂适应系统能否很好地识辨与压缩规律并抛弃偶然性的东西有关。
盖尔曼认为，假定所描述的系统根本没有规律性，一个正常运作的复杂适应系统也就不能发现什么图式，因为图式是对规律性的概述，而这里没有任何规律可言。换句话说，它的图式的长度是零，复杂适应系统将认为它所研究的系统是一堆乱七八糟的废物，其有效复杂性为零。这是完全正确的；胡言乱语的语法图式其长度应该是零。虽然在具有给定长度的比特串中，随机比特串的aici［算法信息量］最大，但是其有效复杂性却为零。([8],p.58)
aic标度的另一个极端情形是，当它几乎等于零时，比特串完全规则，比如全由1组成。有效复杂性一用于描述这样一个比特串的规律性的图式的长度——应该非常接近于零，因为“全部为1”的消息是如此之短。
因此，盖尔曼提出，要想具有很大的有效复杂性，aic既不能太高，也不能太低。换句话说，系统既不能太有序，也不能太无序。有效复杂性是非随机性的，但是有效复杂性又不等于有序中的简单性，即完全规则的那种情况。这里的有效复杂性应该指可理解性意义上的描述长度较长的类。因为可理解性意义的描述长度很短，就相当于简单性了。而完全不可理解，意味着完全随机性。描述长度与事物本身相等，相当于对事物没有认识。有效复杂性一定介于这两者之间。有效复杂性如何才是可以度量的呢？无法准确或定量的度量，是有效复杂性的缺陷之一。当然，有效复杂性一方面是对客观复杂性的有效理解与最小表达，一方面也应该是一个随人类主体认识能力进化而变化的变量。
　　二、对随机性的理解
这里需要对随机性概念进行辨析。研究表明，我们通常在三种“随机性”上使用随机性概念：第一，指该事物或事物之状态非常不规则，找不到任何规律来压缩对它的描述；第二，指产生该事物的过程是纯粹偶然的或随机的过程。而该过程所产生的结果，主要是随机的，其信息不可压缩；有时则可能得出包含一定的规律性，其信息可有一定程序的压缩性；极少情况下能够得出非常规则的结果，其信息具有很大压缩性。第三，指伪随机性过程产生的貌似随机性结果，即事实上该过程是非偶然的决定论过程的，但是其结果却非常紊乱（如混沌）。为避免混淆，盖尔曼建议在英文中用"stochastic"表示随机的过程，用"random"表示随机性的结果。本文所指的随机性是结果的随机性，即"random"。我们现在能够认识的随机性中的规律性的东西，是第二种类和第三种类的一部分性质。即对它们的描述有可以压缩其信息的情况。
这样，所谓随机性即有两种，一种即过程随机性，一种结果或状态随机性。而真正意义的随机性是不仅其产生的结果具有随机性的特征，而且产生的过程也是随机性的过程。混沌只具有结果形态上的貌似随机性，而不具有过程的随机性。
　　三、两类复杂性与随机性关系
由以上关于复杂性的各种描述性定义的探讨，我们可以看出，这里实际上存在着两种关于复杂性完全不同的观点。
观点一，认为“复杂性”相当于随机性。随机性大小是度量认识复杂性的尺度。随机性越多，复杂性越大，完全随机性的信息，则相当于最大复杂性，或根本复杂性。
可以比较一下关于熵的定义，系统内部混乱程度最大，系统熵最大。所以，最大复杂性就相当于最大信息熵。计算复杂性、算法复杂性中相当大的成分包含着这种涵义。像熵，kolmogorov复杂性，以及f.cramer定义的根本复杂性都属于此类复杂性。我认为，此类复杂性的意义对对象本身的复杂性认识没有意义，但是对认识条件下的认识复杂性长度即认识难度却是有意义的，即这种复杂性不是关于认识对象的，而是关于认识能力（如计算机解题所需资源）的。kolmogorov给出了一个对如何度量计算难度有效的“复杂性”概念，但是却使得人们在认识客观对象的复杂性上陷入误区。
观点二，认为“复杂性”不等于随机性，而是胜于随机性的、人们对事物的复杂性的有效认识。
这两类复杂性哪个更科学和准确呢？我们需要仔细研究一下不同情况。我们要证明复杂性不等于随机性，但是复杂性又离不开结果表现为“随机性”的状态。
第一种情况，我通过“同无素的大量粒子组成的体系”的结果简单性表明，随机性不复杂。如气体体系，到达平衡态时，体系熵达到最大。但它复杂呢？不，原因在哪里？实际上，在体系未达到平衡态时，体系内部的分子的微观态存在大量的区别，如速率分布不遵循麦克斯韦分布，这时体系就其微观态的个数多少而言，其微观态个数多，体系是复杂的；但是到了平衡态时，按照麦克斯韦速率分布，绝大多数分子的速率趋于一致，体系的不同的微观态不是增加，而是减少了。故体系进入平衡与均匀，熵趋向最大。到达熵最大时，理想条件下体系的微观态变成全同态，完全一致，没有不同的微观态了。体系因而变得简单了。此时物理学对它可以运用气体定律（实际气体用范德瓦斯气体方程）描述。从信息的程序角度看，描述语句可以写成：


f(p,v,t)=c



换句话说，虽然体系内部此时微观态最随机，但是微观态为全同志，无区别、无演化（体系状态不随时间变化而变化），因此，描述可以极为简单，数据信息可以压缩，即存在着对这种针对全同微观态的统计意义下的简单规律描述。可见，完全随机性的东西不一定复杂，或完全随机性的东西有最简单的情况。因此，把随机性等同于复杂性至少存在反例。

第二种情况，我通过“混沌”的复杂性表明它不是随机性的复杂性。混沌是一种貌似随机的复杂性状态。说它貌似随机，即指它的产生不是随机性(stochastic)所为，而是确定性体系所为。但是它的微观态具有“随机性”(random)，即混沌局域内没有两个相同的状态，这种混沌与平衡态的无序完全不同。此时，体系内部的微观态个数随演化时间长度增加而增加，区别越来越大，越来越多，混沌的程序也随演化时间增加，这样对混沌的全部微观态描述就是不可能的了。然而，属于复杂性态的混沌态却不能作为复杂性等于随机性的证明，因为混沌不是随机性，而是貌似随机性的东西。对此，混沌现象和规律的发现者、美国气象学家洛伦兹作了这样的说明：“我用混沌这个术语来泛指这样的过程——它们看起来是随机发生的，而实际上其行为却由精确的法则决定。”[9]这表明混沌行为的重要属性是确定性，而不是随机性，即对处于混沌行为状态的系统来说，“现有状态完全或几乎完全决定未来，但却不是看上去如此”。那么，确定性的混沌行为为什么会看上去像是随机的呢？他认为，这是因为“在某些动力系统中，两个几乎一致的状态经过充分长时间后变得毫不一致，恰如从长序列中随机选取的两个状态那样。”([9],p.6)
第一种情况和第二种情况还有一个差别，那就是，产生第一种情况的办法是随机性(stochastic)的，因此对其产生过程我们是无法描述的；但是对结果或体系最终结果或体系整个状态我们能够用简单方法（统计方法）加以描述。而产生第二种情况的方法是确定性的，是有其简单性（动力学）方法的，对其产生过程或演化过程的一部分（在有限时间内）我们可以描述，但是对结果或体系最终结果或体系整个状态我们无法加以描述。换句话说，我们无法产生第一种情况，但是能够描述它；我们能够产生第二种情况，但是无法描述它。
这种情况使我想起突变论创始人托姆对“理解”和“行动”的精辟见解。按照托姆的观点，整个科学活动可比作一个连续进行过程，这一过程具有两极。一极代表纯粹知识：其基本目标是理解现实。另一个极涉及行动：其目标是对现实采取有效行动。传统的、目光短浅的认识论不赞成这种两极说，因为要采取有效的行动，总必须先“理解”。相应于这两种对科学所持的相反观点，存在两种不同的方法论。“行动”说在本质上是解决局部的问题，而“理解”说却试图要找到通用解（也即整体解）。明显的矛盾是，求解局部问题需要使用非局部手段，而可理解性则要求将整体现象化为几种典型的局部情况。[10]上述对无序和混沌的复杂性情况的分析告诉我们，这种传统认识论的观点可能是错误的。因为有这样的情况，我们对它已理解透彻，却无力对它采取任何行动。反过来，有时我们对现实世界能采取有效行动，但对其所以有效的原因却茫然无知。几乎可以毫不夸张地说，无序的简单性和混沌的复杂性为这种情况提供了佐证。我们能够产生和控制混沌，但是对混沌复杂性的认识还没有完全转化为盖尔曼意义上的有效复杂性。关于混沌类型的复杂性，我们目前就知之甚少，我们只了解混沌具有对初值的极端敏感性，具有某种类型的吸引子（局域性），混沌具有微观结构。我们计算的越细致，混沌也越反映出层次间的自相似性和嵌套性，它也就越复杂。
我们研究一个问题，一般先要界定清楚问题和环境。如果不能清楚地界定问题，你能拿它怎么办呢？然而，许多复杂性问题都是其内容尚未界定清楚的、并且在不断生成的问题，其环境因时间的推移而不断变化。适应性作用只是对外界对它的回报做出反应，而用不着考虑清楚行动的意义和对行动背后的理解。
复杂性问题的复杂正在于此。作用者面对的是界定不清的问题、界定不清的环境和完全不知走向的变化。只要略想片刻就会认识到，这就是生命的全部含义。人们经常在含糊不清的情况下做出决定，甚至自己对此都不明白。我们是在摸着石头过河，在过河中我们不断改变自己的思想，不断拷贝别人的经验，不断尝试以往成功的经验。
以气象学为例。天气从来不会是一成不变的，从不会有一模一样的天气。我们对一周以上的气候基本上是无法事先预测的，有时1～2天的预报都会产生错误。但我们却能够了解和解释各种天气现象，能够辨认出像锋面、气流、高压圈等重要的气象特征。一句话，尽管我们无法对气象做出完全的预测，但气象学却仍不失为真正的科学。[11]
以上研究表明，第一种类型即所谓随机性的复杂性不是我们要的复杂性，它相当于f.cramer意义的亚临界复杂性（类似简单性），如果把复杂性与这种随机性联系起来，那么说复杂性等于随机性(stochastic)，则是不对的；但是如果是第二种意义的复杂性则与貌似随机性的随机性(random)结果相互关联在一起。那么的确存在随机性越大，似乎越复杂的情况。但是这里需要注意的是，信息熵在这里决不是热力学熵，另外，产生这种复杂性的原因也不是随机性。
所以在说复杂性与随机性的关系时，我们一定要辨别所说的随机性是什么随机性，是stochastic呢，还是random。我们是否可以这样说，复杂性是具有random性态的东西，而不是由stochastic产生的。
　　四、复杂性与状态随机性及其他
在随机性(random)基础上建立起来的复杂性，还应该继续加以分析。我们先暂时去掉第二种随机性(stochastic)，于是这里还存在两种random意义下的随机性。第一种是非常不规则结果，从而找不到任何规律来压缩对它的描述的随机性，另一种是貌似随机性的结果，即由非偶然的决定论过程所产生的，但是其结果却非常紊乱（如混沌）的随机性。在第一种随机性情况下，无法得到对事物的认识，描述长度将同事物本身一样。该事物我们认为复杂吗，如果不复杂为什么我们无法认识？如果承认它不复杂，那么就需要承认除了复杂性成为我们认识的障碍以外，我们认识的障碍还有其他。有其他障碍吗？如果承认其复杂，我们就需要承认世界上存在完全无规则的东西，它无法认识。而这点与我们关于世界是有规律的假定是矛盾的，似乎进入了不可知论。看起来，我们只能等待认识进步来解决该问题。
因此，我建议，在假定这个世界不断演化的前提下，把对应于第一类随机性（非常不规则，而无法压缩信息串）的复杂性称为“潜在复杂性”(potential complexity)，而把对应于第二类随机性（貌似随机性的结果，非常紊乱）的复杂性称为“有效复杂性ⅱ”，以区别盖尔曼的“有效复杂性”。因为盖尔曼把对应于第一种随机性中可认识的复杂性称为“有效复杂性”（我们把它称为复杂性ⅰ），有效复杂性不等于我们对该对象的认识达到了所有细节全部认识完毕，无一遗漏。而是指这种复杂性抓住了该对象的基本方面和特性，使得该对象成为科学研究的实在对象。
这样在随机性(random)背景下的复杂性可以分类为如下：
附图
　　五、余论：一些未解问题
随着对复杂性与随机性关系的讨论深入，我们自然会问：对随机性本身而言，它对认识客观复杂性就没有意义吗？现在最大的问题是，当我们面对一系列“貌似”随机性的东西，我们并不清楚它在演化过程中未来会如何？第一，在更广阔的场景中和更长的时间序列中它是真随机性，还是伪随机性？第二，对一个有限的时间和实践而言，现在它显现为随机性，并不能保证它以后的演化也是随机性的。所以，我们即便认为真随机性中不包含复杂性，我们在有限的时间内也不可能判定事物的后演化过程一定是非随机性的，或随机性的，从而也就无法判断其中是否有意义，即包含有效的复杂性。
另外，如果随机性中不包含有效的意义，我们如何说它复杂呢？这里马上就有一个例子：猴子在计算机键盘上随机地敲出的100万个符号组成的“文本”与莎士比亚的《哈姆雷特》哪个更复杂呢？按照根本复杂性＝最大随机性的观点，那一定是前者复杂于后者；而按照有效复杂性的观点则后者复杂于前者。在与随机性意义的关系上看，如果承认随着思想中包含第一类随机性(stochastic)越大，思想就越复杂的话，我们就得承认疯子的胡乱思想最复杂，因为无法对他的思想加以认识和把握（编程，也许在疯子的思想世界里，被认为可以把握，但是这两个世界即理性世界与非理性世界无法通约，除非一个理性人疯后又恢复为理性人并且没有遗忘疯子的经历和思想），我们也要承认谁的语言最晦涩难懂，谁的理论最复杂。如果认为非随机性的表达有效复杂性的思想才复杂，我们则可利用有效复杂性这个尺度上去度量历史上思想家的理论的复杂性程度。事实上，我们对思想家的思想复杂程度常以其思想深刻、细致和广度，以及是否逻辑自洽和论证充分判定的。我想，比较两个思想的复杂性程度时，可以通过是否对相同思想和思想对象的解读更深入、更细致和更广泛，以及思想体系的层次逻辑四个尺度加以把握，这四个尺度实际是：信息深度、结构层次、细致性、广度（包括问题范围性）。
可见，还是有效复杂性的实际意义更好些。但是一个没有随机性的世界，只有貌似随机性的世界虽然充满了不确定性，但是这却不解渴，我们那些突然的变化，我们那些临时的改变，那些偶然性的东西也是存在的，那么它们对复杂性就没有贡献了吗？如果存在这种贡献，又应该如何计量这种由偶然性或随机性产生的复杂性呢？

【参考文献】
[1]　joel i.seiferas,machine-lndependent complexity theory,[j]handbook of theoretical computer science,edited by j.van leeu wen,elsevier science publishers b.v.,1990,p.165.
[2]　a.n.kolmogorov,three approaches to the definition of the concept'quantity of information',[j]problem of information transmission,1(1965)1.
[3]　g.j.chaitin on the length of progams for computing finite binary sequences,[j]j.acm 13(1966)547.
[4]　r.j.solomonoff,a formal theory of inductive inference,[j]inform.and control 7(1964)1,224.
[5]　ming li,p.m.b.vitányi,kolmogorov complexity and it applications,[j]handbook of theoretical computer science,edited by j.van leeuwen,elsevier science publishers b.v.,1990,p.197.
[6]　r.badii,a.politi,complexity:hierarchical structures and scaling in physics,[m]cambridge university press,1997,p.7.
[7]　f.cramer,chaos and order,the complex structure of living systems,[m],vch,new york,1993,p.214.中译本已由柯志阳、吴彤译出，上海科技教育出版社2000年出版。
[8]　murray gell-mann,the quark and the jaguar,adventures inthe simple and the complex,w.h.freeman & co.,new york,1994,p.44；中译本：〔美〕盖尔曼·夸克和美洲豹——简单性和复杂性的奇遇.[m]长沙：湖南科学技术出版社，1998，第47页。
[9]　〔美〕e.n.洛伦兹著，刘式达等译，混沌的本质，[m]北京：气象出版社，1997.第3页。
[10]　〔法〕勒内·托姆.突变论：思想和应用，[m].上海：上海译文出版社，1989，第141页。
[11]　〔美〕m.沃尔德罗普：复杂（陈玲译），[m]北京：三联书店，1997，第356-357页。