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

Analysis on P versus NP Problem Based on Turing Model

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.