汉语是联合国官方正式使用的 6 种同等有效语言之一。请不要歧视汉语！

Chinese is one of the six equally effective official languages of the United Nations.

Not to discriminate against Chinese, please!

[请教] P对NP（二）：结果的相对性与“1+3”种证明

求教心切，由于种种原因，下文里面错误难免。

请您不吝批评与指教！衷心感谢！

主要相关数学分支：公理集合论，图论，概率论；以及理论计算机科学。

Key words:  P vs NP Problem,  The P versus NP Problem,  polynomial-time,  NP-complete,  NP-completeness,  set theory,  Zermelo–Fraenkel set theory,  ZF,  axiom of power set,  independence

   在 2012-03-23，《[请教] P对NP：请郝克刚教授等专家指教（一）》里，向老师们汇报了我在“P对NP”方面的一般背景知识，以及无穷化版本下的“P对NP”，等。

   转眼10年已过。

   下面向老师们汇报一下 2012-03-23 之后的新情况。感谢老师们的批评指正！

一、P对NP：为什么出现“相对性”的结果？

   本节要点提示：

   一般而言，求解“某问题”得到的答案，与采用的“工具”有关。

   简言之：问题的答案，往往依赖于工具。

   一个“类比”的解释：

   中学时期，实系数一元二次方程，在根的判别式 < 0 时，有没有解？ 

   显然：

   ① 对于初中生，在实数域：无解。

   ② 对于高中生，在复数域：有解。

   再通俗些：

   一位老人，在一个饭店吃饭后，要不要付饭钱？

   ① 一般的老人，应该付饭钱。

   ② 如果老人是饭店老板的爸爸，可以不付饭钱！

   数学，是对现实世界中数量关系和空间形式的抽象后进行研究的一门学问。

   严格地说，数学不是科学。

   数学不具备自然科学所要求的“客观性”，一般也不能通过“科学实验”进行判定。

1.1  数学证明的两种基本类型：归纳、演绎

   数学证明可以分成两大类：归纳、演绎。

   归纳证明，以“数学归纳法”为代表。数学里，采用归纳证明的定理数量相对较少。

   演绎证明，是数学里常见的证明。

   《Encyclopedia of Mathematics》里对演绎证明的阐述：

   A reasoning conducted according to certain rules in order to demonstrate some proposition (statement, theorem); it is based on initial statements (axioms). In practice, however, it may also be based on previously demonstrated propositions. Any proof is relative, since it is based on certain unprovable assumptions.

   引用自： Proof. A.S. Kuzichev (originator), Encyclopedia of Mathematics. https://encyclopediaofmath.org/wiki/Proof

   意思是：

   为了证明某个命题（陈述、定理）而按照一定的规则进行的推理；它基于初始陈述（公理）。然而，在实践中，它也可能基于先前证明的命题。任何证明都是相对的，因为它是基于某些无法证明的假设。

1.2  演绎证明的局限性、证明过程的基本特征

   前提蕴含的命题，才能通过演绎进行证明。

   1931年，哥德尔是这么说的：

   在任何包含最少算术（+，⋅，符号 ∀，∃，以及处理它们的通常规则）的一致形式系统中，都可以找到形式上不可判定的命题，即这样的封闭公式 A 和 ¬A 都不能在系统内推导出来。

   原文在：Gödel incompleteness theorem. Encyclopedia of Mathematics.

https://encyclopediaofmath.org/wiki/G%C3%B6del_incompleteness_theorem

   后来，1974年 Gregory John Chaitin 说的更细致：

   1. 在一个具有 n 位公理的形式系统中，不可能证明复杂度大于 n+c 的特定二进制字符串。

   2. 相反，在一些具有 n+c 位公理的形式系统，其中可以确定每个复杂度小于 n 的字符串和每个字符串的复杂度，并且也可以表示出每个复杂度大于或等 n 的字符串，但无法知道每个字符串的复杂度超过 n 的程度。

   3. 不幸的是，任何可以确定每个复杂度小于 n 的字符串的形式系统，都存在一个严重问题或另一个问题。如果它的公理位很少，则需要难以置信长的证明；要想一个很短的证明，则要求公理的位数难以置信地多。我们说“难以置信”，是因为这些数量比  n 的任何可计算函数增长得更快。

   详见：[1] Gregory John Chaitin. Information-theoretic computation complexity [J]. IEEE Transactions on Information Theory, 1974, 20(1): 10-15. DOI: 10.1109/TIT.1974.1055172 , https://ieeexplore.ieee.org/document/1055172

   我的一些初步介绍：

   2022-03-01，[科普 + 备课] Chaitin定理（1966年）

https://blog.sciencenet.cn/blog-107667-1327564.html

   我自己认为， Chaitin 定理大体上是孔子、老子下面观点的“现代逻辑方式”的阐述：

   《论语·卫灵公》：工欲善其事，必先利其器。

   《道德经》第五十四章：故以身观身，以家观家，以乡观乡，以邦观邦，以天下观天下。吾何以知天下然哉？以此。

   具体到“P对NP”，根据 Chaitin 定理可以认为：

   （1）问题的答案，依赖于采用怎样的数学“形式系统”。

   （2）你用的数学“形式系统”能力越强，证明的过程就越短。

1.3 “P对NP”的相对化答案

   ① 在 NDTM 中 P 等于 NP；For a NDTM,  P = NP ;

   ② 在 DTM 中 P 不等于 NP；For a DTM,  P ≠ NP ;

   ③ 没有关于所采用的理论计算机模型的必要说明，则具有独立性。

二、P对NP：共计 1+3 种证明

   本节要点提示：

   1个直接证明，NDTM 相当于 DTM 的幂集。

   3个“弱”证明：（1）立体图导致NPC；（2）无穷版本下，NDTM的基数是c，DTM的基数是a。（3）概率化证明，尚未发表。

   1个直接证明，请看《A non-canonical example to support that P is not equal to NP [J]. Transactions of Tianjin University, 2011, 17(6): 446-449.》

2.1 “弱”证明之一：立体图导致NPC

   3SAT 是 NPC，里面会有 Kuratowski 图（Kuratowski graph） K₅, K_3,3。

   2SAT 是 P，里面不会 Kuratowski 图（Kuratowski graph） K₅, K_3,3。

2.2 “弱”证明之二：无穷化

   无穷版本下，NDTM 的基数是 c，DTM的基数是 a。

   承认集合论 ZF 里的幂集公理（Axiom of power set），即可。

2.3 “弱”证明之三：概率化

   还没有公开发表。这里就无法汇报了。

参考资料：

[1] Kazimierz Kuratowski, Andrzej Mostowski. 【K. Kuratowski and A. Mostowski】 Set theory: with an introduction to descriptive set theory [M]. 2nd completely rev. ed. Amsterdam : North-Holland Pub. Co. ; New York : Distributor, Elsevier/North-Holland, 1976.

[2] Frank Harary. Graph Theory [M]. Boca Raton: CRC Press, 1969. 

https://www.taylorfrancis.com/books/mono/10.1201/9780429493768/graph-theory-frank-harary

DOI:  https://doi.org/10.1201/9780429493768

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

http://vip.hnadl.cn/article/detail.aspx?id=1140345

https://d.wanfangdata.com.cn/periodical/ChlQZXJpb2RpY2FsQ0hJTmV3UzIwMjIwNDE1Eg5RSzAwMDAwMjM4OTQwOBoIZ3ZnOWhicWc%3D

[4] Science 125 个科学前沿问题系列解读，《科学通报》：  季铮锋, 夏盟佶. 计算的极限[J]. 科学通报, 2016, (4): 404-408.

https://blog.sciencenet.cn/blog-528739-963412.html

https://blog.sciencenet.cn/blog-528739-1179598.html

https://blog.sciencenet.cn/blog-528739-963412.html

https://www.sciengine.com/collections/ArchivesDetail/9m5bnbuLAkFzva5yJ;JSESSIONID=59809ece-8507-4055-aca8-5190a322107f

https://www.sciengine.com/CSB/article?doi=10.1360/N972015-01363&scroll=

[5] SCIENCE, 2005-01-07, Special Issue 125th Anniversary, 125 Questions: what don't known?  [EB/OL]. 01 JULY 2005, VOL 309, ISSUE 5731

https://science.sciencemag.org/content/309/5731

[6] Charles Seife. What Are the Limits of Conventional Computing? [J]. Science, 2005, 309(5731): 96-97.

DOI:  10.1126/science.309.5731.96

https://www.science.org/doi/10.1126/science.309.5731.96

[7] Mathematics. Encyclopedia of Mathematics [EB/OL].

https://encyclopediaofmath.org/wiki/Mathematics

[8] ZFC. Encyclopedia of Mathematics [EB/OL].

https://encyclopediaofmath.org/wiki/ZFC

[9] P vs NP Problem [EB/OL] - Clay Mathematics Institute

http://claymath.org/millennium-problems/p-vs-np-problem

[10] Roger Sperry. Some effects of disconnecting the cerebral hemispheres [J]. Science, 1982, 217(4566): 1223-1226. 

DOI: 10.1126/science.7112125

https://www.science.org/doi/10.1126/science.7112125

[11] Gregory John Chaitin. Information-theoretic computation complexity [J]. IEEE Transactions on Information Theory, 1974, 20(1): 10-15. DOI: 10.1109/TIT.1974.1055172

https://ieeexplore.ieee.org/document/1055172

我的主要相关论文：

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

doi：10.3969/j.issn.1673-5692.2011.04.009

http://www.cqvip.com/QK/87495A/201104/39096952.html

https://mall.cnki.net/magazine/Article/KJPL201104010.htm

https://d.wanfangdata.com.cn/periodical/dzkxjspl201104009

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

https://doi.org/10.1007/s12209-011-1593-5

https://link.springer.com/article/10.1007/s12209-011-1593-5

相关链接：

[1] 2012-03-23，[请教] P对NP：请郝克刚教授等专家指教（一）

https://blog.sciencenet.cn/blog-107667-550859.html

[2] 2022-06-06，1999《哲学研究》一文观点的“一句话”概括

https://blog.sciencenet.cn/blog-107667-1341799.html

[3] 2022-04-07，[科普] ST, SSS, STS, STEM, STEAM, STREAM：能不厌学吗？

https://blog.sciencenet.cn/blog-107667-1332910.html

   “科学 Science，技术 Technology，工程 Engineering，数学 Mathematics”

感谢您的指教！

感谢您指正以上任何错误！

感谢您提供更多的相关资料！