复杂性的各种“定义”
同信息论的奠基过程相比,复杂性的刻画已经走过更长的道路,却远远未臻完备。根本的原因在于不存在复杂性的绝对尺度。不界定基本的框架,根本不能就复杂性问题对话,更休提进行科学分析。人们已经提出过不下30种各有其适用范围的复杂性“定义”,这里举示若干。 历史上较早提出的是计算复杂性概念,它源于20世纪30年代数学逻辑的一些深刻命题。每个问题都有其特定的规模N,如货郎担问题有必须访问的村庄数目,或是需要求逆的矩阵的阶。解决问题所需的代价(如计算时间),如何随问题规模N变大而增长?若代价的增长不超过N的某个幂次或多项式,该问题是简单的,属于P(即多项式)类。若增长速率超过N的任何多项式,则问题是艰难的,属于NP类。严格地说,若已知某NP问题的解,可付出P类代价加以演示;但若要找到这个解,则须付出NP代价。若两个NP问题可用P代价彼此转换,则它们是同等艰难的。这些等价的NP问题构成所谓NP完备类。目前已经知道上千个NP完备问题。同属于P类的问题,其代价比例于N的对数或平方,仍是一种实际差别。把一种算法从N改进到log N,或者证明对某个问题不存在比N2更好的算法,都是严肃认真的科学成果。计算复杂性的研究有专门期刊[10],以及许多书籍和会议文集。 算法复杂性是1964-1966年由索洛莫诺夫(R. J. Solomonoff)、科尔莫戈罗夫(A. N. Kolmogorov)和柴廷(G. J. Chaitin)分别独立提出的。粗略地说,算法复杂性就是产生特定的图形花纹(或符号序列)的最短程序的长度与图形花纹(或符号序列)本身的大小之比的极限——当后者趋向无穷时的极限。这里“长度”和“大小”均按二进制位数计,而“程序”则是在普适的理论计算机上执行。 以一个二进制数,如1101110010100110100001011001110011010111110…为例。不难明白,上述算法复杂性其实是随机数的一种判据。为写出实质上比给定数更短的程序,须利用该数包含的某些规律。若无规律可循,依定义该数就是随机的,相应的最短程序只能是在打印语句中照抄该数。程序长度比该数多出PRINT五个字母,取无穷极限后就没有差别了。算法复杂性等于1,就是最随机的无法压缩的图形花样。这是一种深刻的思想,但一般说来,它是不可操作的:是否存在比该数字更短的程序,往往无法确定。不仅如此,下面将说明,算法复杂性并没有解决复杂性的比较问题。 回到产生曼德勃罗集合的复数迭代。它的程序是很简短的。要看到复杂的细节,必须长时间迭代。迭代愈久,细节的复杂层次愈多。因此,有人引入“逻辑深度”的概念,即以在普适计算机上执行前述最短程序的指令步数或时钟拍数,来比较不同图形的复杂程度。这是把计算复杂性和算法复杂性结合起来的度量。不过,它也还没有解决问题。 从复数退回到实数,回到前面提到的抛物线迭代。对于参数a和初值x0的无穷多种选择,这种迭代会导致混沌轨道。用相同的程序,执行同样多的步数,在两个不同参数下得到的同样长的混沌轨道,其复杂性有差别吗?如果不能回答这样简单明确的问题,就不能奢望去刻画更普遍的复杂性。所幸的是,可以通过符号动力学建立运动轨道和形式语言的联系,然后借助语法复杂性理论确切地回答一部分这类问题。 在抛物线映射中,忽略轨道点的具体数值,只注意它是落在抛物线最高点的左面还是右面,相应地把数值换成字母L或R。于是,数字轨道变成符号序列,迭代动力学成为符号动力学。这实际上就是物理学里经常实行的粗粒化描述。不同程度的粗粒化,舍去更小层次上的细节,有利于突出更根本的行为。适当地粗粒化,有助于得出更严格的结论。事实上,粗粒化考虑是把人们引向复杂性问题研究的一项深刻纲领。