基于图灵模型的P=?NP问题分析  

Analysis on P versus NP Problem Based on Turing Model

作　　者：杨晓艳[1] 童亚拉[1] 

机构地区：[1]湖北工业大学理学院,湖北武汉430068

出　　处：《计算机时代》2011年第12期1-2,5,共3页Computer Era

摘　　要：P=?NP问题是计算复杂性中的核心问题。2000年,美国克雷实验室将其收录为"千禧年大奖"七个问题之首。本文基于图灵模型,对P=?NP问题的研究现状、P=NP/P≠NP证明方法、NPC问题求解方法及研究进展进行阐述。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.

关 键 词：图灵机 P类 NP类 NPC问题 

分 类 号：TP301.5[自动化与计算机技术—计算机系统结构]