中国科技大学校长朱清时院士关于复杂性理论的外行错误

　　柔能

　　最近看了jxh：《朱清时院士胡说围棋名局》，指出朱清时院士在《用现代
科学观看中医和中国传统文化》一文中关于围棋说了外行话后，我也拜读了朱院
士的文章。发现他在有关复杂性理论的陈述中，也同样有严重的外行错误。

　　他是这样说的：

　　【代数复杂性的概念可以作复杂性的现代定义的例子。至少在某种程度上，
一个系统的状态可以用一系列数据来描述，这些数据可用数字表示，它们构成一
个数列，因此我们只要定义这种数列的复杂性就行了。
　　考虑一个具体例子，比如:l、4、9、16、25、36等数字构成的数列，我们发
现这个数列可以由自然数n的平方得到。
　　每当给出一个数列时，我们就进行类似的研究，确定是否存在一个计算机程
序和一组初始数据(为了规范,假设均为图灵机)，用它们可以计算出整个数列？
它们若存在并能表达出来，则程序和初始数据的最短长度便是代数复杂程度的量
度；若它们的长度大得难以表达（甚至不存在)，则这样的系统就称为复杂系
统。】
　　（原文见
http://news.ustc.edu.cn/studentwork/default.asp?ArticleID=7873）

　　他用中学数学中的数列的概念构想了一个“代数复杂性的理论”。而且还煞
有介事地说“…为了规范，假设均为图灵机”。从这些文字可以断定朱院士对图
灵机和复杂性理论缺乏最基本的了解，否则他绝说不出“程序和初始数据的最短
长度便是代数复杂程度的量度”这样错误的外行话。如果是我的学生在他的考试
卷中这样来解释复杂度，我肯定会毫不客气地给他零分。我相信中国科技大学计
算机科学系肯定会有不少教授和研究生是了解计算理论的，当得知他们的校长这
样来解释复杂度后，不知做作何感想！

　　计算复杂性理论是研究解决一类问题的算法的复杂性度量的一门理论性很强
的学科。通常是用图灵机作为算法的模型。简单地说，如果能够证明某图灵机的
求解过程所花费的时间（即步数）少于问题描述字（即初始字）长度的某给定函
数，则称这个函数是此算法的时间复杂度。例如，如果这个函数是多项式函数，
就说这个算法具有多项式时间复杂度；如果这个函数是指数函数，就说这个算法
具有指数时间复杂度。显然指数时间复杂度的算法就比多项式时间复杂度的算法
复杂。

　　顺便说一句，如果用P表示所有能用确定的图灵机在多项式时间解决的问题
类，用NP表示所有能用非确定的图灵机在多项式时间解决的问题类，P类是否等
同于NP类（P=NP？）就是著名的现在尚未解决的世界难题，美国克莱研究所2000
年把它列为七大各悬赏一百万美元的世纪难题之之一。

　　当然，在现在科学技术发展如此迅速，学科门类繁多，专业分工很细的情况
下，不可能苛求一个专家，甚至院士，对他的专业以外的领域也很精通。但是有
一条原则是大家必须遵守的，那就是踏踏实实的治学态度。知之为知之，不知为
不知。不懂就是不懂，不要装懂。更不能乔装大家，冒充博学，在没有做扎实研
究的基础上凭想当然妄谈学科交叉。在当前这种急功近利、浮躁虚夸作风在学术
界盛行的时期，作为一位校长和院士应当为树立良好学风做出表率，而不是相反。