||
汉语是联合国官方正式使用的 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) K5, K3,3。
2SAT 是 P,里面不会 Kuratowski 图(Kuratowski graph) K5, K3,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
[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/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”
感谢您的指教!
感谢您指正以上任何错误!
感谢您提供更多的相关资料!
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-10-7 22:34
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社