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

博文

英语博客:P vs NP - The perplexity of Nondeterminism

已有 3338 次阅读 2017-8-25 05:50 |个人分类:不确定性问题和算法讨论|系统分类:科研笔记| 英语博客

最近德国波恩大学的计算机科学家Nobert Blum声称证明了“P/=NP” [1],再次引发学术界对世纪难题“P vs NP”的关注与讨论。事实上,此问题不仅是计算机理论的基本问题,更与如今蓬勃发展的人工智能的基本理论问题密切相关。

“P vs NP”反应的是计算机领域最基本的“确定性问题与不确定性问题”的关系问题,然而由于流行的NP定义中“不确定性”的消失,使得“P vs NP”问题的研究始终处于停止不前的状态,我们已博客中与大家一起讨论了与此相关的各种议题,今天我们又开通了英语博客“P vs NP - The perplexity of Nondeterminism (https://nptheory.blogspot.fr)”,希望在更大的范围内和国际同行进行更加广泛的讨论,欢迎大家一起参加!

[1]“最新证明面临质疑:P/NP问题为什么这么难?”(https://mp.weixin.qq.com/s?__biz=MzIyNDA2NTI4Mg==&mid=2655416878&idx=2&sn=4b9cb0389ec607144cf3f2ab748197d7&chksm=f3a67043c4d1f955349d9d89f27a21fa4a84961894ae92f5b8651cc8d98bd6cdba8c42540d61&mpshare=1&scene=1&srcid=0817CHhpQKADQfcTdnK3bKam&pass_ticket=Kqkmi0Mtv%2Ffif%2FVEir7fCFGAsY5uaty8u%2Bpl7JWf%2Fs%2FSO37P2u6wG6SuA3mUNGMv#rd)  


附英语博客的第一篇文章:

P vs NP- Loss of "Nondeterminism"

- 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 vs NP had not yet been resolved. (Hemaspaandra)
- Things have their roots and branches, affairs have their end and beginning. When you know what comes first and what comes last, then you approach the "Tao". (The Great Learning "大学")
________________________________________

The P vs NP problem is said to be the most notorious problem in theoretical computer science, and it was also designated as one of seven Millennium Problems by the Clay Mathematics Institute [1].
NP is initially put forward as concept relative to P. However, in the current theoretical framework, NP is defined as problems polynomial time decidable by Nondeterministic Turing Machine (NDTM), and equivalently polynomial time verifiableby Deterministic Turing Machine (TM). As such properties are shared by P, so such a NP contains P. Consequently, P vs NPproblem consists in asking whether NP is equals to P since NP contains P. Although a lot of efforts have been done to try to solve this problem, it remains an open century problem [2][3].
Recently the mathematics professor Norbert Blum from Bonn (Germany) claimed to solve it in his paper "A Solution of the P vs NP Problem", and now computer scientists around the world are examining his work [4]. In fact, this problem has also drawn attention to the lay people, for example, in May 2 2013, the New Yorker published an article entitled as "A Most Profound Math Problem" [5].
On the one hand, more and more people are interested in this problem, but on the other hand the understanding about it is increasingly confused. In this sense, the P versus NP problem is not only the curiosity of the public, but also the perplex of experts in computer science, as expressed by Hemaspaandra when he introduced Gasarch's second poll about the P vs NP problem [6].
Peter Drucker, "the founder of modern management", said that “The most serious mistakes are not being made as a result of wrong answers. The true dangerous thing is asking the wrong question.” Then, why is the problem so important? Because the problem is the root of cognition and behavior of human, and the whole branches of thought and action are then developed from this root, that is, the definition of a problem is to create the realm which we face and deal with.
Concerning the P vs NP problem, we think that the key to this problem is not to answer whether NP is equals to P or not, but to ask what NP is, because the current definitions of NP have cancelled the concept of that real « NP » relative to « P », which we call the loss of nondeterminism from NP.
We create this blog for the purpose of providing a space of exchanging the reflexions and works about the P vs NPproblem from different points of view for all peoples who are interested in this problem, and hope to contribute to the progress of this problem. Moreover, from a broader point of view, we hope to contribute to the integration of science and culture as well as Chinese thinking and Western philosophy.
Reference :
[2] Stephen Cook, The complexity of theorem proving procedures. Proceedings of the Third Annual ACM Symposium on Theory of Computing. pp. 151-158 (1971). (http://theory.stanford.edu/~trevisan/cs172-07/cook.pdf)
[3] S. Aaronson.  P=?NP [PDF], in Open Problems in Mathematics (Springer), 2016. ECCC TR17-004.
[4] P-NP-PROBLEM : New attack on the biggest mystery of computer science (https://steemit.com/science/@n3bul4/p-np-problem-new-attack-on-the-biggest-mystery-of-computer-science)
[6] The Second P =? NP Poll1 William I. Gasarch (http://www.cs.umd.edu/~gasarch/papers/poll2012.pdf)




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

上一篇:亚眠博物馆之夜
下一篇:亚眠“科学节”——围棋从中国到法国的旅行
收藏 IP: 82.246.87.*| 热度|

3 梅卫平 杨正瓴 姜咏江

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

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

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

GMT+8, 2024-3-29 05:33

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部