P 与 NP 问题研究-《计算机技术与发展》

文章信息/Info

Keywords:: the seven great mathematical problems; deterministic turing machines; nondeterministic turing machines; NP complete problems

摘要:: P 与 NP 问题被列为七大世界数学难题之首,由于其相关概念抽象而复杂,许多该领域的学生学者,对其相关概念的理解存在谬误,不少已发表的研究论文都体现了这一谬误.用中文通俗讲解到底什么是 P 和 NP 问题以及它们的关系,透过抽象的定义揭示其本质.列举一些科研论文上常见的对 P 和 NP 问题理解上的谬误,通过分析揭示其错误实质.同时并对解决这一问题可能的研究方法作一综述,对研究前景做一展望,为在该方向上学习和研究的学生学者,提供有价值的参考.由于文中包括:对复杂抽象的概念进行通俗而深入的剖析,对已有的研究进展进行概括,对未来可能的研究方法和研究路线进行综述和分析,故能对该领域的研究者在概念的正确把握、文献的查阅和研究方向的选择上提供助益

Abstract:: P versus NP is the first one of the famous seven great mathematical problems in this world. Because the concepts about them are very abstract and complicated,some scholars and students in computer science often misunderstand them. A lot of published papers con-tain these misunderstandings. It explains these concepts in Chinese clearly. By deeply studying their definitions,reveal their essence. List a lot of misunderstandings of these concepts and analyse them. Also survey the research methods and foresee the research future of this field,so as to give an assistance to this field's people. It contains:to analyze the complex and abstract concepts in an easy way,to pick up important points from a lot of products,to survey and analyze the methods for the future study,so it can help the researchers in this field for all the above aspects