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

博文

Bill Gasarch关于“P versus NP”前途的二次调查

已有 4926 次阅读 2015-1-5 22:46 |个人分类:不确定性问题和算法讨论|系统分类:论文交流| versus, NP理论, 中西文化互补

“P versus NP”是计算机领域中一个平凡又不凡的问题。说“平凡”,是因为此问题缘起于探讨有效求解大量的应用问题,诸如:旅行商问题,图染色问题,作业调度问题等等;说“不凡”,是因为此问题是计算机理论的核心问题,又是Clay Mathematics Institute收录的七个千禧年难题之一,虽然学术界已投入了巨大资金和人力,至今却没有实质性的进展。

Bill Gasarch于2002年和2012年(http://www.cs.umd.edu/~gasarch/papers/poll2012.pdf),对100和152计算机理论前沿的研究者,进行了关于“P versus NP”前途的调查,是对该问题现状的很好解读。Hemaspaandra在介绍2012的调查时,悲观地说:
-我希望在遥远的未来,人们读到这四篇文章,可以帮助他们了解,在P versus NP还没得到解决的黑暗年代里人们的思想状态。
( I hope that people in the distant future will look at these four articles to help get a sense of people’s thoughts back in the dark ages when P versus NP had not yet been resolved. )

我们的“NP理论”工作就是针对此问题的探索,我们认为此问题实际上隐含着一直未被人们重视的认知偏差,以致于成了名副其实的「皇帝的新衣」,我们希望借此工作能引起人们对认知基本问题的重视,以及对中西文化互补性的实践和思考,。。。

文章“什么是NP?- 解读中国哲学悖论“白马非马(What is NP? - Interpretation of a Chinese paradox white horse is not horse)”,就是我们工作的第一阶段的一个总结,希望与感兴趣的同事切磋交流。此外,这里出现的一些观点、术语等,会与流行的有所不同,以后逐步介绍。



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

上一篇:“NP理论”研究的缘起
下一篇:什么是NP?- 解读中国哲学悖论"白马非马"
收藏 IP: 82.246.87.*| 热度|

2 杨正瓴 icgwang

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

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

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

GMT+8, 2024-11-23 04:26

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部