【内容提要】本文通过对历史上复杂性与随机性关系的认识回顾，展示和分析了起源于计算机科学领域的kolmoorov复杂性与随机性的直接关联，分析了盖尔曼的有效复杂性概念，论证了两种复杂性与随机性的关系，以及随机性的不同情况，力图剥离混合在复杂性与随机性相互关系上的一些误读和误解，还复杂性与随机性一种客观的本真关系。
关键词】复杂性/计算复杂性/算法复杂性/随机性/有效复杂性ⅰ/有效复杂性ⅱ
正文】
最近，我们在研究复杂性问题的过程中，发现复杂性与随机性的关系具有特别的意义，许多国内外的学者在复杂性与随机性的关系认识上，常常以随机性代替复杂性，认为随机性就是复杂性的内容之一。本文力图剥离混合在复杂性与随机性相互关系上的一些误读和误解，还复杂性与随机性一种客观的本真关系。 一、历史上复杂性与随机性的认识回顾
科学上经典的复杂性的概念，最早起源于计算机科学研究领域，当然它主要参考了物理学当时的基本观念。
（一）建基随机性上的两种复杂性概念
为了探索复杂性与随机性的关系，我们先了解计算复杂性、算法复杂性的概念。
首先让我们从信息理论的角度来看待问题。信息的简单还是复杂涉及的是表达信息的序列串如何。简单的非复杂系统的产生指令很简短，通常也很明显：例如，所有项相加即为和。这样复杂性可以操作性地定义为：寻最小的程序或指令集来描述给定“结构”——一个数字序列。这个微型程序的大小相关于序列的大小就是其复杂性的测量。
青年文学家 序列111111…是均匀的（不复杂的）。对应的程序如下；在每一个1后续写1。这个短程序使得这个序列得以延续，不管要多长都可以办到。
序列110110110110…的复杂性高一些，但仍然很容易写出程序：在两个1后续写0并重复。甚至序列110110100110110100…也可以用很短的程序来描述；在两个1后续写0并重复；每三次重复将第二个1代之以0。这样的序列具有可定义的结构，有对应的程序来传达
信息。比较这三个一个比一个复杂些的序列。再看下面的序列11010010110111010010…，它不再是一个可识别的结构，若想编程必须将它全部列出。但是如果它是完全随机性的，那么，我们根据概率规则，可以知道最终在这个数串中0和1的出现几乎是等概率的。
于是为了解决这些关于如何认识复杂性增长和判别复杂性程序的问题，科学家们定义了多种描述性的复杂性概念。
计算复杂性(putational plexity)源于20世纪30年代数学逻辑发展过程中提出的一些深刻命题。它们都有自己特定的问题规模n，计算复杂性就是指解决问题随问题规模n增长而需要的代价增长。这种简单性和复杂性的分野是，如果计算时间（或空间）的增长不超过n的某个幂次或多项式，那么该问题是简单的，称为p类问题。如果增长速率超过n的任何多项式，则问题是困难的，称为np类（np即“非确定多项式”nondeterministic polynomial的缩写）问题，即复杂性问题之一。如推销商的路线选择问题（travellin selesman problem，简称tsp）就属于问题中的“完全np”一类问题。此类问题的特点是，随着问题涉及面增加，其计算量将指数性或失控式地增长。
汇率指数
图灵机 对计算复杂性的常见度量是时间和空间。一般地说，所谓时间就是一个计算中离散步骤的数目；空间就是指计算指令读取独特的存储地址的数目。[1]如前所述，时间上的计算复杂性即一个计算机描述一个系统（或解一个问题）所需要的时间；空间上的计算复杂性即描述一个系统所需要的计算机存储量。
imac
算法复杂性(alorithmic plexity)，主要是由a.n.kolmoorov,[2].j.chaitin[3]和r.j.solomonoff[4]在20世纪60年代中期分别独立提出的概念，又称为kolmoorov复杂性。基本思想和定义如下：
对每一个d域中的对象x，我们称最小程序p的长度丨p丨就是运用指定方法s产生的关于对象x的复杂性。对计算机s而言，设给定的符号串为x，将产生x的程序记为p。对一个计算机来说，x是输入，p是输出。粗略的说，关于一个符号串x的kolmoorov复杂性，就是产生x的最短程序p的长度。上述定义可写为：[5]
k[,s](x)=min｛丨p丨:s(p)=n(x)｝
k[,s](x)=∞ 如果不存在p.中国新闻出版报
人民日报七一社论
其中k[,s](x)即kolmoorov复杂性。后一个公式的含义是明显的，即如果传送的符号串完全杂乱无章，不到任何规律（即程序p），那么，复杂性就等于符号串本身，而符合串是无规无穷数，复杂性即无穷。因此在算法复杂性中，实际上是越随机性(random)的东西，越不可认识，其结果是它越复杂。换句话说，复杂的随机性对象有最大的复杂性，因为不可能压缩对其对象的描述。[6]
（二）kolmoorov复杂性的影响和有效复杂性的提出
kolmoorov复杂性定义实际上支配了后来计算机科学上对复杂性的几乎所有的研究，以后又波及到几乎所有科学领域。例如，f.cramer就是按照这种思路把复杂性程度分为三个等级：亚复杂性、临界复杂性和根本复杂性。所谓亚临界复杂性是指系统表面复杂但其实很简单，或许是算术性的。简单的物理定律，如牛顿定律可以用于得到的决定性系统；所谓临界复杂性是指在复杂性的特定阶段——在它的临界值上——开始出现某些结构。最简单的情况是对流和对流图案形式。这个复杂度称为临界复杂性。这些系统构成一些亚系统，例如进化系统或不可逆热力学系统；所谓根本复杂性是指“只要系统有着不确定性解或混沌解它就是根本复杂的”，[7]“一旦程序的大小变得与试图描述的系统可以相提并论，不能再
对系统进行编程。当结构不可辨识时——即当描述它的最小算法具有的信息比特数可与系统本身进行比较时——我称之为根本复杂性。根本复杂性的这个定义是以a.n.kolomoorov(1965)的方程为基础的。”([7],p.211)
按照f.cramer的认识，根本复杂性相当于无法认识。根本复杂性即那些表现得完全随机性（random或stochastic）、描述结果与被描述对象可以相提并论，完全无法获得规律性认识，简单地说，无法辨识即根本复杂性。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议