中國科技大學校長朱清時院士關於複雜性理論的外行錯誤

　　柔能

　　最近看了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
年把它列為七大各懸賞一百萬美元的世紀難題之之一。

　　當然，在現在科學技術發展如此迅速，學科門類繁多，專業分工很細的情況
下，不可能苛求一個專家，甚至院士，對他的專業以外的領域也很精通。但是有
一條原則是大家必須遵守的，那就是踏踏實實的治學態度。知之為知之，不知為
不知。不懂就是不懂，不要裝懂。更不能喬裝大家，冒充博學，在沒有做紮實研
究的基礎上憑想當然妄談學科交叉。在當前這種急功近利、浮躁虛誇作風在學術
界盛行的時期，作為一位校長和院士應當為樹立良好學風做出表率，而不是相反。