◇◇新语丝(www.xys.org)(xys.dxiong.com)(xys.3322.org)(xys.xlogit.com)◇◇ 朱清时也许还是看了点书的 雅诗 下面朱清时的这段话(引自柔能的文章)非常有趣。  【代数复杂性的概念可以作复杂性的现代定义的例子。至少在某种程度上, 一个系统的状态可以用一系列数据来描述,这些数据可用数字表示,它们构成一 个数列,因此我们只要定义这种数列的复杂性就行了。   考虑一个具体例子,比如:l、4、9、16、25、36等数字构成的数列,我们发 现这个数列可以由自然数n的平方得到。   每当给出一个数列时,我们就进行类似的研究,确定是否存在一个计算机程 序和一组初始数据(为了规范,假设均为图灵机),用它们可以计算出整个数列? 它们若存在并能表达出来,则程序和初始数据的最短长度便是代数复杂程度的量 度;若它们的长度大得难以表达(甚至不存在),则这样的系统就称为复杂系 统。】   这段话有趣的地方是把几种复杂度理论揉在一起了。图林机与最主要最基本 的复杂度理论, NP 理论(见柔能的文章),联系在一起。代数复杂性(复杂 度?)的英文为 algebraic complexity 吧, 也是一个很重要的理论, 跟 NP 理论有一定联系,考虑的也是计算所需要的时间空间等等。朱院士举的例子考虑 的是程序的长度,却有点像 Kolmogorov complexity (wiki 如下), 哈哈. 像 那个斜眼的笑话了。 不过也许朱院士自己是明白的,只不过说得太通俗, 反而 让一些人(如我)糊涂了。 http://en.wikipedia.org/wiki/Kolmogorov_complexity In computer science, the Kolmogorov complexity (also known as descriptive complexity, Kolmogorov-Chaitin complexity, stochastic complexity, algorithmic entropy, or program-size complexity) of an object such as a piece of text is a measure of the computational resources needed to specify the object. (XYS20070128) ◇◇新语丝(www.xys.org)(xys.dxiong.com)(xys.3322.org)(xys.xlogit.com)◇◇