数学证明的长度：与公理系统能力负相关

杨正瓴

（天津大学电气与自动化工程学院，天津市  300072）

1 基本含义

“工欲善其事，必先利其器”（《论语·卫灵公》），以及“故以身观身，以家观家，以乡观乡，以邦观邦，以天下观天下。吾何以知天下然哉？以此。”（老子《道德经》第五十四章），早就说明“工具越强，劳动量越低”这样一个朴素的道理。

这个道理在数学证明中的具体体现，就是特定定理（命题）证明过程的长度问题。可能B. Russell在1906年，D. Hilbert等人在1928年就考虑了这类问题。看上去1936年K. Gödel的Über die Länge von Beweisen（On the length of proofs）是最早的专门文献。1966-1974年Gregory J. Chaitin提出的定理，被认为是哥德尔第一不完全性定理（Gödel's first incompleteness theorem）的信息论形式下的具体化。Chaitin定理的第三条说：

Unfortunately, any formal system in which it is possible to determine each string of complexity less than n has either one grave problem or another. Either it has few bits of axioms and needs incredibly long proofs, or it has short proofs but an incredibly great number of bits of axioms. We say “incredibly” because these quantities increase more quickly than any computable function of n.

Chaitin定理的第三条的基本意思是：对特定命题，如果在一个信息量小的公理系统（few bits of axioms）里证明，则证明的过程或长度是很大的。反过来，想要得到短的证明（short proofs），则必须在一个信息量很大的公理系统（an incredibly great number of bits of axioms）里。这和“工欲善其事，必先利其器”的道理是一致的。

目前的数学命题证明（过程），往往是数百页的长度。如Andrew Wiles对费马大定理的证明。以及对四色定理计算机证明的批评：“一个好的数学证明应当像一首诗——而这纯粹是一本电话簿！（A good mathematical proof is like a poem - this is a telephone directory!）”这种长的数学证明，除了数学问题的难度本身引起之外，另一种可能的原因是：证明所采用的数学理论的信息量太小。

Grigori Perelman对Poincaré conjecture证明的核心，大约十页。这说明合适的理论，是可以缩短数学证明长度的。

采用信息量大的数学理论进行证明，是缩短证明长度的主要策略之一。

2 两个例子

2.1 矩阵乘法

以n阶有理数方阵为例，由于矩阵乘法定义中的加法会引起lgn的进位位，所以对于两个“独立因素”的方阵，定义包含的必须信息量为O(n³×lgn)。换言之，不存在比O(n³)更小的时间复杂性。

以Strassen算法为代表的O(n^2+ε)类方法，核心是“把多个乘法合并在一起”计算。在数字计算机上，这几乎必然导致计算结果误差的增大。其极限是1990年陈道琦、谢友才、应文隆在科学通报发表的《关于矩阵乘法的一个最佳算法》。该方法只用一次乘法，但需要W(n³×lgn)的有效数字位数。

2.2 “P对NP”

“P对NP”（P versus NP, P vs NP）问题当前研究与证明的主流方法主要有三大类：对角化diagonalization、电路复杂性circuit complexity、证明复杂性proof complexity。它们都是比较弱小的数学理论，所以在里面证明“对确定型图灵机P≠NP”的难度极大（incredibly long proofs）。

换成信息量大的ZF（Zermelo–Fraenkel set theory），则不难发现：幂集公理（Axiom of power set）直接引起康托定理（Cantor theorem）。由于“非确定型图灵机的状态数”可以是“它对应的确定型图灵机的幂集”，所以P≠NP。准确地说，“P对NP”是个相对性的问题，不存在抽象的确定答案。接受ZF，则有“对确定型图灵机P≠NP”；反过来，不接受ZF，“P对NP”的答案则是需要进一步的具体考虑。

参考文献：

[1] B. Russell [1906] The theory of implication, American Journal of Mathematics, 28, pp. 159-202.

[2] D. Hilbert and W. Ackermann [1928] Grundzüge der theoretischen Logik, Springer-Verlag, Berlin.

[3] K. Gödel [1936] Über die Länge von Beweisen, Ergebnisse eines Mathematischen Kolloquiums, pp. 23-24. English translation in Kurt Gödel: Collected Works, Volume 1, pages 396-399, Oxford University Press, 1986.

[4] Pavel Pudlák [1998] The lengths of proofs, in Handbook of Proof Theory, S.R. Buss ed., Elsevier, pp.547-637.

[5] Gödel incompleteness theorem, Encyclopedia of Mathematics, http://www.encyclopediaofmath.org/index.php/G%c3%b6del_incompleteness_theorem.

[6] Gregory J. Chaitin [1974] Information-theoretic computational complexity. IEEE Transactions on Information Theory, IT-20, pp. 10-15.

[7] 杨东屏[1993] 哥德尔不完全性定理剖析, 曲阜师范大学学报：自然科学版, 19(1): 31-36.

[8] Andrew Wiles [1995] Modular elliptic curves and Fermat's Last Theorem, Annals of Mathematics (Annals of Mathematics), 141(3): 443-551.

[7] 杨正瓴[2011] “P对NP”难题研究的形转换新思路, 科学智慧火花, http://idea.cas.cn/viewdoc.action?docid=9402.

[8] 杨正瓴 [2011] 第二类计算机构想. 中国电子科学研究院学报, 6(4): 368-374.

[9] YANG Zhengling (杨正瓴) [2011] A non-canonical example to support that P is not equal to NP. Transactions of Tianjin University, 17(6): 446-449.

[10] Cantor theorem, Encyclopedia of Mathematics, http://www.encyclopediaofmath.org/index.php/Cantor_theorem.

[11] ZFC (Zermelo–Fraenkel set theory with the axiom of choice), Encyclopedia of Mathematics, http://www.encyclopediaofmath.org/index.php/ZFC.

相关链接：
[1] 俗解Chaitin定理
http://bbs.sciencenet.cn/home.php?mod=space&uid=107667&do=blog&id=478066

[2] 矩阵乘法需要O(n^3)的时间，不能再减少
http://bbs.sciencenet.cn/blog-107667-725846.html