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

博文

不确定性问题(NP)与“不确定性”- 基本定义的一个简要解释

已有 8505 次阅读 2016-11-28 13:23 |个人分类:不确定性问题和算法讨论|系统分类:科研笔记| 不确定性, 不确定性问题(NP)

李红雨等诸网友的提问集中在我们将NP定义为“不确定性问题”上。李红雨实际上是在问:“不确定性”有很多意义,我们为何能统一为NP这个概念?所以这是在认知意义上提问:自然语言中的“不确定性”究竟指什么?

自然语言中的“不确定性”确实有各种不同的意义,这才会有李红雨提到的不同层次上的“不确定性”问题,也就是说自然语言中,“不确定性”的意义本身就是“不确定的”,从这个意义上理解,我们所定义的“不确定性问题(NP)”在自然语言中也是意义一致的,就是说,正是由于人们所知道的不确定性的问题具有各种不同的“不确定性”的意义,所以“不确定性问题(NP)”这个概念与“不确定性”本质才一致。在最终的意义上,“不确定性”是人的本质的不确定性。

到现在为止,我们的研究是在“不确定性问题(NP)”这个概念内进行的,而且已经把“算法”领域中的研究推进到逻辑学意义上的“判断”层次。对“不确定性”这个概念的研究,已经涉及到如人工智能、智能哲学等更深广的领域,但所有这些研究所基于的“确定性”的标准是数学和计算机意义的“(能行)可计算性,effectively calculability, computability”,即被人们广泛接受的共识:著名的丘奇-图灵论题。

所以,李红雨认为“如果(NP)问题至少可以用指数时间来判定,也仍然是确定的,尽管对于计算机来说可能是个难得问题”所代表的观点,我们认为在表达上有问题。以“可计算性”概念为标准:NP就是不可判定的,也就是没有“确定性的解”,我们正是在与“可计算性”这个标准相对的意义上定义NP的;从这个标准出发,认为“NP有确定性的解”就是不正确的,首先就是把以“可计算性”意义为标准的NP偷换成了认知意义上以自然语言表达的“不确定性的问题”,正如上文所说,在自然语言中的“不确定性”的意义本身就具有不确定性,只有在讨论中清晰地保证概念的一致性并避免层次上的混乱,才不会发生概念上的混淆;其次,把以算法“可计算性”意义上定义的NP概念换成日常语言中的“不确定性的问题”,实际上所付出的代价就是把P意义的“确定性解”换成了具体的可接受的“近似解”,即把数学意义上的“变量”换成了具体机器能接受的“常量”,这也就是我们所说的“NP-算法”,即现在一般所称的各种启发式算法,这与我们的定义也是相容的。

正因为我们是在“可计算性”的严格意义上定义NP的,所以我们NP理论的基石是可计算性理论,须追溯到图灵1936年最初的工作(见图灵1936年论文解读系列文章:http://blog.sciencenet.cn/home.php?mod=space&uid=2322490&do=blog&classid=171716&view=me&from=space)。

 




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

上一篇:NP理论(5):不确定性问题(NP)研究中的层次与中国传统逻辑
下一篇:再谈为什么质疑NP的“可验证定义”
收藏 IP: 82.246.87.*| 热度|

5 杨正瓴 张能立 李红雨 wangbin6087 xlsd

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

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

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

GMT+8, 2024-4-25 01:07

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部