不确定性的困惑与NP理论分享 http://blog.sciencenet.cn/u/liuyu2205 平常心是道

博文

师徒对话 - “算法的存在性”与“解的存在性”的层次 (2012/6/2)

已有 605 次阅读 2022-7-27 02:35 |个人分类:师徒对话|系统分类:科研笔记

师:这封信集中讲问题(判断)、算法与(计算)这三个层次的两种不同关系,你已经基本理解清楚了,现在主要是如何具体的进行知识的表达:解释或阐释。


首先,这三个概念在外延分类上,是要求严格区分的,这是作为知识的基本要求,也是现在人们通常的使用这三个概念的方法;第二,从它们的本质,也就是内涵的意义上说,这三个概念是层次包含的,(从这里可以窥见阐释这个概念与通常的解释的区别):包含在算法内,算法包含在问题内,所以我们使用这些概念时,应当留意自己是在那种意义上在用或理解这个术语,但我们又不能在每次使用一个术语前都加上修饰性定义,这也是在数学理论中采用严格的形式化定义的原因,形式化的表达能够有效地防止歧义,但这种形式化的理论是一种理论达到成熟时才能达到的阶段,所以通常写专业文章和读专业文章,大都是为达到一种共识而进行的努力,一个术语或概念的相同或不同,本身就是很难如意地表达的,如何在解释阐释之间变易,是学者无穷递进的上升阶梯。


NP理论中计算判断的关系特别地具有上述的层次性,比如4整除的正整数问题,直觉上,作为问题是被理解为整除法的算法的,而作为算法是被理解为整数解的,因为我们已经有了P算法(上帝给的),所以这里没有P算法是否存在的判断问题,我们说P算法与P问题同一,这就是指只须处理作为整除法的算法之间的具体的求解关系,这里不是那种不能判定算法的存在,而必须先求解算法的问题。


对于NP理论来说,我们连求解”NP问题 算法都没有,所以没有能力直接面对求具体的这样的层次,只能求解NP问题的NP算法,NP问题和NP算法这两个层次成为NP理论的核心,所以我们才会说,NP问题与NP算法在分类意义上的层次不同,但在内涵上具有层次上(本质)的一致性,以区别于P问题与P算法的同一性,但无论怎样小心,仍不能在日常语言的表达方式上精确地使用这些概念和表达方法,所以对作者和读者都要求通过反复表达和理解,以得到形成一种共同的语境,形式化的表达只不过是最后可以得到的精确化的结果。


这里顺便说一下大家都熟悉的故事,奈尔大学的Hubert Chen博士提供了一个玩笑式的“P不等于NP的证明”1反证法,设P = NP。令y为一个P = NP的证明。证明y可以用一个合格的计算机科学家在多项式时间内验证,我们认定这样的科学家的存在性为真。但是,因为P = NP,该证明y可以在多项式时间内由这样的科学家发现。但是这样的发现还没有发生(虽然这样的科学家试图发现这样的一个证明),我们得到矛盾。


这里有两个层次:首先是假设存在一个超能科学家的存在,然后,是这个科学家如何证明P=NP的过程,这两者不能混淆,假设具有上帝能力的科学家存在和他如何运用假设方法去证明P=NP是两个层次,前者是算法存在或算法能力的层次,后者是运用这个算法能力去求解的层次,前者层次可以包含后者层次,但后者不能包含前者,前者是假设知识理论能够最终解决P=NP问题,这是对当前这种算法是否存在这种判断性成问题的的情况下的一种超能假设,后者则是在这个算法的存在不成问题的前提下,证明或求解P=NP的过程,即具体算法如何构造。


我们通常使用的假设是在一个算法存在的前提下的假设,比如,x整除4时,我们可以假定解为y,这是合理的,因为整除算法具有得到这个具体的解的能力;但假设一个能证明P=NP的科学家的存在,就是假设能解决最困难的问题的算法或算法能力的存在,这种假设中隐含了一种事先的肯定,就是说,假设一个不存在的东西的存在与肯定这个东西的实际存在,具有相同的哲学意义——这是一个关键点——假设了一种肯定性!由于算法的存在包含了运用这个算法求解这个层次,所以很容易造成以后者的假设肯定前者的存在的混乱,这种混乱一直存在在现在流行的NP理论中,所以上述玩笑中假设一个超能科学家的存在没有实质意义,这只是玩笑而不是反证法,实际上,我们对用以证明P=NP的证明方法(算法)是否存在的判断无法回答,所以根本谈不上如何去证明或求解P=NP具体过程,由此看出,在这种的情况下去构造一种证明P=NP的算法是不可能实现的。


这个例子在业界是尽人皆知的了,在迷惑和不迷惑之间迷惑或不迷惑,也特有意思,你可以充份熟习一下,在讲堂上或在自己的网站上能给你带来许多FANS的。


参考文献:

1Hubert Chen has a webpage (https://www.cs.cornell.edu/hubes/pnp.htm2003) with a really short argument that "P-not-equal-to-NP":
"Proof by contradiction. Assume P=NP. Let y be a proof that P=NP. The proof y can be verified in polynomial time by a competent computer scientist, the existence of which we assert. However, since P=NP, the proof y can be generated in polynomial time by such computer scientists. Since this generation has not yet occurred (despite attempts by such computer scientists to produce a proof), we have a contradiction."






https://m.sciencenet.cn/blog-2322490-1348901.html

上一篇:师徒对话 - “阐释学” (2015/4/19)
下一篇:“真理”与“可证明性” - Jean-Yves Girard

2 尤明庆 杨正瓴

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

数据加载中...
扫一扫,分享此博文

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

GMT+8, 2022-10-7 13:56

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部