| 查看: 1747 | 回复: 2 | |||
YANGZL金虫 (小有名气)
|
[交流]
“P对NP（P versus NP, P vs NP）”问题的描述、难度、可能的答案
|
|
“P对NP（P versus NP, P vs NP）”问题的描述、难度、可能的答案 关键词：P对NP，P versus NP，P vs NP，the Millennium Problems，Clay Mathematics Institute “The P versus NP problem is to determine whether every language accepted by some nondeterministic algorithm in polynomial time is also accepted by some (deterministic) algorithm in polynomial time.” [1], now it becomes a famous mathematical fundamental problem, though it was being a hard open problem in the field of computational complexity theory in the theoretical computer science since the early 1970’s [2]. “P vs NP Problem” or “P versus NP problem” becomes one of the most famous mathematical problems after the seven Millennium Problems released by Clay Mathematics Institute in 2000 [3]. Before this, in 1998, Steve Smale listed it as the third problem in his 18 great problems of the 21th century, i.e, “Problem 3: Does P=NP?” [4]. After this, in 2005, Science magazine listed it as the 19th question of its top 25 of the 125 big questions face scientific inquiry over the next quarter-century, i.e., “What are the limits of conventional computing?” [5]. P≠NP is the mainstream perspective up to now. In 2002, a total of 100 people poll gave the following statistics [6]: “ 1. 61 thought P≠NP. 2. 9 thought P=NP. 3. 4 thought that it is independent. While no particular axiom system was mentioned, I assume they think it is independent of ZFC. 4. 3 just stated that it is NOT independent of Primitive Recursive Arithmetic. 5. 1 said it would depend on the model. 6. 22 offered no opinion.” About 6000 papers each year discuss the “NP-complete” or “P vs NP” [7], the recent reviews and papers can see [8-12], et al. 参考文献： [1] COOK S. The P versus NP Problem, official problem description, [EB/OL]. http://www.claymath.org/millennium/P_vs_NP/pvsnp.pdf [2] 中国大百科全书•电子学与计算机[M]. 北京: 中国大百科全书出版社, 1986. Encyclopaedia of China • Electronics and computer [M]. Beijing: Encyclopaedia of China Publishing House, 1986. (in chinese) http://202.112.118.40:918/web/index.htm [3] THE CLAY MATHEMATICS INSTITUTE. P vs NP Problem [EB/OL]. http://www.claymath.org/millennium/P_vs_NP/. [4] SMALE S. Mathematical problems for the next century [J]. Mathematical Intelligencer, 1998, 20(2): 7-15. [5] SEIFE C. What are the limits of conventional computing? [J]. Science, 2005, 309(5731): 96. [6] GASARCH W I. The P=?NP poll [J]. SIGACT News, 2002, 33(2): 34-47. [7] ALLENDER E. A status report on the P Versus NP question [J]. Advances in Computers, 2009, 77: 117-147. [8] FORTNOW L. The Status of the P versus NP Problem [J]. Communications of the ACM, 2009, 52(9): 78-86. [9] COOK S. The importance of the P versus NP question [J]. Journal of the ACM, 2003, (50)1: 27-29. [10] GASSNER C. Oracles and relativizations of the P =? NP question for several structures [J]. Journal of Universal Computer Science, 2009, 15(6): 1186-1205. [11] MANEA F, MARGENSTERN M, MITRANA V, PEREZ-JIMENEZ MJ. A new characterization of NP, P, and PSPACE with accepting hybrid networks of evolutionary processors [J]. Theory of Computing Systems, 2010, 46(2): 174-192. [12] MUKUND M. NP-Completeness not the same as separating P from NP [J]. Communications of the ACM, 2009, 52(4): 9-9. [13] KURATOWSKI K, MOSTOWSKI A. Set theory [M]. Amsterdam: North-Holland Publishing Company, 1976. [14] HAZEWINKEL M. Encyclopaedia of mathematics: an updated and annotated translation of the Soviet “Mathematical encyclopaedia”[M]. Dordrecht: Kluwer Academic Publishers, 2001. 《苏联数学百科全书》，http://eom.springer.de/ [15] HOPCROFT J E, MOTWANI R M, ULLMAN J D. Introduction to automata theory, languages, and computation (Third edition) [M]. New Jersey: Addison Wesley, 2006. [16] GAREY M R, JOHNSON D S. Computers and Intractability: A Guide to the Theory of NP-Completeness [M]. New York: W. H. Freeman, 1979. [17] Nondeterministic Turing Machine [EB/OL]. http://mathworld.wolfram.com/NondeterministicTuringMachine.html [18] CHAITIN G J. Information-theoretic computational complexity [J]. IEEE Transactions on Information Theory, 1974, 20(1): 10-15. [19] 中国大百科全书•数学[M]. 北京: 中国大百科全书出版社, 1988. Encyclopaedia of China • Mathematics [M]. Beijing: Encyclopaedia of China Publishing House, 1988. (in chinese) http://202.112.118.40:918/web/index.htm |
回复此楼» 猜你喜欢
2025冷门绝学什么时候出结果
已经有3人回复
-
天津工业大学郑柳春团队欢迎化学化工、高分子化学或有机合成方向的博士生和硕士生加入
已经有4人回复
-
康复大学泰山学者周祺惠团队招收博士研究生
已经有6人回复
-
AI论文写作工具：是科研加速器还是学术作弊器？
已经有3人回复
-
孩子确诊有中度注意力缺陷
已经有6人回复
-
2026博士申请-功能高分子，水凝胶方向
已经有6人回复
-
论文投稿，期刊推荐
已经有4人回复
-
硕士和导师闹得不愉快
已经有13人回复
-
请问2026国家基金面上项目会启动申2停1吗
已经有5人回复
-
同一篇文章，用不同账号投稿对编辑决定是否送审有没有影响？
已经有3人回复
» 本主题相关价值贴推荐，对您同样有帮助:
p-NPP法测定脂肪酶活性p-NP标准曲线问题
已经有9人回复- 【转帖】关于NP，NP-hard，P，NPC等相关问题的讨论
已经有13人回复
- 【讨论】哥德巴赫猜想可以有哪些应用
已经有33人回复
YANGZL
金虫 (小有名气)
- 应助: 4 (幼儿园)
- 金币: 15155.4
- 帖子: 253
- 在线: 488.4小时
- 虫号: 1422023
- 注册: 2011-09-29
- 性别: GG
- 专业: 电力系统
2楼2021-07-23 01:15:52
YANGZL
金虫 (小有名气)
- 应助: 4 (幼儿园)
- 金币: 15155.4
- 帖子: 253
- 在线: 488.4小时
- 虫号: 1422023
- 注册: 2011-09-29
- 性别: GG
- 专业: 电力系统
|
有些概率分布，如 Weibull Distribution Exponential distribution Logarithmic Distribution Log-normal Distribution 自变量取值都是正的实数。 根据Central limit theorem，当 sums or other functions of a large number of independent or weakly-dependent random variables have a probability distribution close to the normal distribution. 当项数越来越大时，趋向于正态分布。 |
3楼2021-07-23 02:08:43