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

博文

概念的“相对性”

已有 4806 次阅读 2016-1-5 12:09 |个人分类:不确定性问题和算法讨论|系统分类:科研笔记| 概念, versus, 相对性, “P, NP”

基本概念的定义往往是最困难的,其内涵甚至是无法表达的,比如“存在”、“自我”、“文化”诸概念,只能通过理论的展开呈现出来,NP这个概念也大抵如此,须通过对现有观念的解读,讨论的逐步深入,方有望形成具有共识的定义。

这里,我们谈谈概念的“相对性”。定义的基本功能是界定某待定事物,揭示其本质,将之与其他已知的相关事物区分开,即定义具有“相对性”,换句话说,定义一个概念时,是相对已知概念而言的。

比如“单身汉”这个概念,是相对“非单身汉”而言的,所以在定义“单身汉”时,我们关心的是单身汉与非单身汉之间的区别。一个单身汉首先是一名“男子”(为方便语言的表达,这里仅指男性单身汉),但更重要的属性是“未婚”,正是“未婚”将单身汉与非单身汉区分开的,于是“未婚”是单身汉的本质,故“单身汉”可定义为“未婚男子”,却不能定义为“男子”,也就是说,当问:什么是单身汉?不能回答:单身汉是男子,否则就无法判断一新人是否是单身汉了。

像“单身汉”这样有确定论域的概念,其“相对性”显而易见,人们不会犯将“单身汉是男子”作为“单身汉”定义的认知错误,然而当涉及到一些最基本的、内涵尚不明确的概念时,概念的“相对性”这一重要的常识,往往被人们忽视,成为认知盲点,比如NP。

实际上,“P versus NP”表达的就是“P相对NP”,但是流行观念却把“可验证性”作为NP的本质来定义NP:NP是多项式时间可验证的问题,然而“可验证性”是P和NP共有的属性,并非NP的本质,不过是计算求解一个问题所必须具备的条件罢了(见博文:我们为什么说“确定型图灵机”不是“非确定型图灵机”的特例?)!

中国著名的哲学命题“白马非马”,正是借“白马”的话题对概念定义的“相对性”作一般性的讨论。“白马”作为概念,是相对“黑马、黄马”而言的,也就是说,“白色”是将白马与黑马、黄马区分开的特征属性,但若将“马形”作为“白马”的特征属性来定义白马,说“白马是马”,那么“白马”就失去了其本质“白色”,正是在此意义上,公孙龙说“白马非马”(见博文:NP二个流行定义与“白马非马”)。

由此可见,将“NP是多项式时间可验证的问题”作为NP的定义,犯了类似于将“马”作为“白马”的定义、“男子”作为“单身汉”的定义的认知错误,是有“白马非马”千古迷思、“P versus NP”世纪难题,。。。




https://blog.sciencenet.cn/blog-2322490-948213.html

上一篇:NP是可计算的吗?- “算法”的二个层次
下一篇:“确定性” versus “不确定性”
收藏 IP: 82.246.87.*| 热度|

5 姜咏江 杨正瓴 刘钢 ssmmachen zjzhaokeqin

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

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

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

GMT+8, 2024-12-24 10:09

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部