NP完全问题研究及前景剖析

摘要：

P vs. NP是理论计算机领域最重要的课题之一,而其中的核心是NP完全问题. 由于该问题所涉及的概念复杂抽象,对它们的理解存在不少谬误,许多已发表的研究论文都包含着这些谬误. 主要是:NP、NP完全概念理解谬误,确定性及非确定性图灵机的概念模糊不清,P与NP关系的误读,NP问题研究方向的误导等. 本文分析了这些谬误,并揭示了相关概念的实质. 通过不同角度多方位分析,对NP完全问题可能的解决途径和研究方向,提供了启发式思路.

关键词：确定性图灵机、非确定性图灵机、NP完全问题

所属期刊栏目：37

分类号：TP3-0(计算技术、计算机技术)

资助基金：湖北省自然科学基金项目2014CFC1121

在线出版日期：2015-11-25（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：73-78