| 基于图灵模型的P=？ NP问题分析 |
| |
| 引用本文： | 杨晓艳,童亚拉.基于图灵模型的P=？ NP问题分析[J].计算机时代,2011(12):1-2,5. |
| |
| 作者姓名： | 杨晓艳 童亚拉 |
| |
| 作者单位： | 湖北工业大学理学院,湖北武汉,430068 |
| |
| 摘 要： | P=？NP问题是计算复杂性中的核心问题。2000年，美国克雷实验室将其收录为“千禧年大奖”七个问题之首。本文基于图灵模型，对P=？NP问题的研究现状、P=NP／P≠NP 证明方法、NPC问题求解方法及研究进展进行阐述。
|
| 关 键 词： | 图灵机 P类 NP类 NPC问题 |
Analysis on P versus NP Problem Based on Turing Model |
| |
| YAN Xiao-yan,TONG Ya-la.Analysis on P versus NP Problem Based on Turing Model[J].Computer Era,2011(12):1-2,5. |
| |
| Authors: | YAN Xiao-yan TONG Ya-la |
| |
| Affiliation: | (School of Science,Hubei University of Technology,Wuhan,Hubei 430068,China) |
| |
| Abstract: | P versus NP problem is the focus in the field of,computational complexity theory. In 2000, the problem is considered to be the first one of seven Millennium Prize Problems by Clay Mathematics Institute. Based on Turing model, the research status of the P versus NP problem, the methods of proving P=NP or P NP, the solution to NPC problem, and the progress of study on P versus NP problem are expounded. |
| |
| Keywords: | Turing machine class P class NP NPC problem |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
