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

博文

[立此存照] 假如有人宣称证明了“P≠NP”,似乎只能证明他们不懂“什么是数学证明”

已有 2407 次阅读 2023-1-18 15:40 |个人分类:科学 - 艺术 - 本质|系统分类:科研笔记

[立此存照] 假如有人宣称证明了“P≠NP”,似乎只能证明他们不懂“什么是数学证明

                                     

一、数学证明的两种基本类型

   (1)归纳证明。以数学归纳法为代表。

   (2)演绎证明。最常见的数学证明。

              

二、演绎证明的局限性

(1)演绎证明:实质是与其采用的“公理”之间的一致性。

   《Encyclopedia of Mathematics 数学百科全书》对“Proof 证明”的解释

   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. Rules of conducting a reasoning and methods of proof form a main topic in logic.

   【机器翻译】为了证明某一命题(陈述、定理)而根据一定规则进行的推理;它基于初始陈述(公理)。然而,在实践中,它也可能基于先前证明的命题。任何证明都是相对的,因为它是基于某些无法证明的假设(公理)。推理规则和证明方法是逻辑中的一个主要课题。

             

(2)哥德尔不完全性定理Chaitin定理

   请看下面推荐的文献。

           

(3)一个直观小例子

   实系数一元二次方程,当跟的判别式 <0 时,有没有解?

   ① 对于初中生,数域解。

   ② 对于高中生,在数域解。

                  

   再通俗些:

   一位老人,在一个饭店吃饭后,要不要付饭钱?

   ① 一般的老人,应该饭钱。

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

                         

   所以,演绎证明的结果,依赖于其证明采用的“具体的公理系统”。因此,演绎证明具有相对性。

                          

工欲善其,必先利其又如不误砍工。

                                                 

参考资料:

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

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

[2] Proof. A.S. Kuzichev (originator), Encyclopedia of Mathematics. 

https://encyclopediaofmath.org/wiki/Proof

   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. Rules of conducting a reasoning and methods of proof form a main topic in logic.

[3] Gödel incompleteness theorem. Encyclopedia of Mathematics.

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

[4] 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

https://dl.acm.org/doi/10.1109/TIT.1974.1055172

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

https://kns.cnki.net/KCMS/detail/detail.aspx?dbcode=CJFD&filename=QFSF199301005

[6] 哆嗒数学网,2022-11-21 10:07,张益唐零点问题论文会是什么结果?

http://blog.sciencenet.cn/u/bonjourgl

   6、 论文是错误的,也被发现具体错误,证明失败。

   经典案例:布卢姆声明证明P≠NP

   2017年德国波恩大学的计算机科学家布卢姆传了一份38页长的论文,声称证明了P≠NP。但不久后业内专家发表看法,说论文中的关键步骤有着核心错误。布卢姆承认错误,收回论文。实际上,多年来有很多人声明解决了P vs NP 问题,但都被发现证明过程有误。这个问题依旧是开放问题。

[7] 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=

[8] 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

[9] 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

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

https://encyclopediaofmath.org/wiki/Mathematics

[11] Michael R. Garey, David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness [M]. New York: W. H. Freeman, 1979.

https://dl.acm.org/doi/10.5555/578533

相关链接:

[1] 2013-10-04,数学证明的长度:与公理系统能力负相关 精选

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

[2] 2022-02-19,[科普 + 备课] 哥德尔不完全性定理(1931年)

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

[3] 2022-03-01,[科普 + 备课] Chaitin定理(1966年)

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

[4] 2010-03-09,逻辑方法的局限性:Gödel incompleteness theorem和Chaitin theorem

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

[5] 2015-03-30,[求助] 哥德尔(Kurt Gödel )一句话的英文原文

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

[6] 2010-03-10,逻辑方法的局限性:元知识、乌龟塔与盲人摸象

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

[7] 2023-01-17,[说明] 我对“P对NP”的所有研究,使用的都是现有的主流数学理论

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

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

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

                 

感谢您的指教!

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

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



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

上一篇:[说明] 我对“P对NP”的所有研究,使用的都是现有的主流数学理论
下一篇:祝大家兔年(2023)春节快乐!
收藏 IP: 123.151.21.*| 热度|

8 尤明庆 叶晓明 宁利中 刘进平 伍赛特 杜占池 朱晓刚 许培扬

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

数据加载中...

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

GMT+8, 2024-3-29 03:20

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部