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

• 作者: 杜立智 符海东 陈和平
• 来源期刊: 武汉工程大学学报
• 学科: 工学
• 关键词: 确定性图灵机 非确定性图灵机 NP完全问题
• 年，卷（期）: 2015,（10）
• 页码范围: 73-78
• 页数: 6页
• 分类号: TP3-0
• 字数: 6235字
• 语种: 中文
• DOI: 10.3969/j.issn.1674-2869.2015.10.014

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈和平	武汉科技大学计算机科学与技术学院	105	1251	17.0	31.0
2	符海东	武汉科技大学计算机科学与技术学院	35	199	7.0	12.0
3	杜立智	武汉科技大学计算机科学与技术学院	21	73	4.0	7.0