| 查看: 1949 | 回复: 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 |
回复此楼» 猜你喜欢
让我中一个面上吧！
已经有16人回复
-
放榜前的不淡定
已经有17人回复
-
科研孤儿太难了
已经有19人回复
-
能否退出参与的面上项目解除限项
已经有9人回复
-
明天应该可查了！？
已经有4人回复
-
什么时候开奖？
已经有11人回复
-
范进中举一文的中心思想
已经有6人回复
-
建议基金发布提前给出明确的时间点
已经有14人回复
-
2026国自然函评费到账
已经有17人回复
-
2026年的国家社科基金项目通讯评审的新规则与新动向、新挑战
已经有5人回复
» 本主题相关价值贴推荐，对您同样有帮助:
- p-NPP法测定脂肪酶活性p-NP标准曲线问题
已经有9人回复
- 【转帖】关于NP，NP-hard，P，NPC等相关问题的讨论
已经有13人回复
- 【讨论】哥德巴赫猜想可以有哪些应用
已经有33人回复
YANGZL
金虫 (小有名气)
- 应助: 4 (幼儿园)
- 金币: 15988.4
- 帖子: 253
- 在线: 521.5小时
- 虫号: 1422023
- 注册: 2011-09-29
- 性别: GG
- 专业: 电力系统
2楼2021-07-23 01:15:52
YANGZL
金虫 (小有名气)
- 应助: 4 (幼儿园)
- 金币: 15988.4
- 帖子: 253
- 在线: 521.5小时
- 虫号: 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
20
