求真分享 http://blog.sciencenet.cn/u/zlyang 求真务实

博文

[请教] P对NP(二):结果的相对性与“1+3”种证明

已有 1677 次阅读 2022-6-10 15:35 |个人分类:基础数学-逻辑-物理|系统分类:科研笔记

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

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 ¬都不能在系统内推导出来。

   原文在: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 等于 NPFor a NDTM,  P = NP ;

   ② 在 DTM  P 不等于 NPFor 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 的基数是 cDTM的基数是 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”

                               

感谢您的指教!

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

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



https://wap.sciencenet.cn/blog-107667-1342404.html

上一篇:[讨论] 磁场矢量带ID,点积、叉积来处理
下一篇:往日(10):低阶非线性变换
收藏 IP: 202.113.11.*| 热度|

13 尤明庆 李宏翰 杨学祥 王涛 刘炜 王毅翔 郑永军 孙颉 范振英 许培扬 宁利中 贾玉玺 周少祥

该博文允许注册用户评论 请点击登录 评论 (5 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2022-8-18 07:08

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部