|本期目录/Table of Contents|

[1]杜立智,陈和平,符海东.ＮＰ完全问题研究及前景剖析[J].武汉工程大学学报,2015,37(10):73-78.[doi:10. 3969/j. issn. 1674-2869. 2015. 10. 014]
　,ＮＰ－ｃｏｍｐｌｅｔｅ ｐｒｏｂｌｅｍ ａｎｄ ｉｔｓ ｆｕｔｕｒｅ[J].Journal of Wuhan Institute of Technology,2015,37(10):73-78.[doi:10. 3969/j. issn. 1674-2869. 2015. 10. 014]
点击复制

ＮＰ完全问题研究及前景剖析(/HTML)
分享到：

《武汉工程大学学报》[ISSN:1674-2869/CN:42-1779/TQ]

卷:
37
期数:
2015年10期
页码:
73-78
栏目:
机电与信息工程
出版日期:
2015-10-31

文章信息/Info

Title:
ＮＰ－ｃｏｍｐｌｅｔｅ ｐｒｏｂｌｅｍ ａｎｄ ｉｔｓ ｆｕｔｕｒｅ
文章编号:
1674-2869(2015)10-0073-06
作者:
杜立智; 陈和平; 符海东
武汉科技大学计算机科学与技术学院，湖北 武汉 ４３００６５
Author(s):
ＤＵ Ｌｉ－ｚｈｉ; ＣＨＥＮ Ｈｅ－ｐｉｎｇ; ＦＵ Ｈａｉ－ｄｏｎｇ
Ｃｏｌｌｅｇｅ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， Ｗｕｈａｎ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， Ｗｕｈａｎ ４３００６５， Ｃｈｉｎａ
关键词:
确定性图灵机; 非确定性图灵机; ＮＰ完全问题
Keywords:
ｄｅｔｅｒｍｉｎｉｓｔｉｃ ｔｕｒｉｎｇ ｍａｃｈｉｎｅ; ｎｏｎｄｅｔｅｒｍｉｎｉｓｔｉｃ ｔｕｒｉｎｇ ｍａｃｈｉｎｅ; ＮＰ－ｃｏｍｐｌｅｔｅ ｐｒｏｂｌｅｍ
分类号:
ＴＰ３－０
DOI:
10. 3969/j. issn. 1674-2869. 2015. 10. 014
文献标志码:
A
摘要:
Ｐ ｖｓ． ＮＰ是理论计算机领域最重要的课题之一，而其中的核心是ＮＰ完全问题. 由于该问题所涉及的概念复杂抽象，对它们的理解存在不少谬误，许多已发表的研究论文都包含着这些谬误. 主要是：ＮＰ、ＮＰ完全概念理解谬误，确定性及非确定性图灵机的概念模糊不清，Ｐ与ＮＰ关系的误读，ＮＰ问题研究方向的误导等. 本文分析了这些谬误，并揭示了相关概念的实质. 通过不同角度多方位分析，对ＮＰ完全问题可能的解决途径和研究方向，提供了启发式思路.
Abstract:
Ｐ ｖｅｒｓｕｓ ＮＰ ｉｓ ｏｎｅ ｏｆ ｔｈｅ ｍｏｓｔ ｉｍｐｏｒｔａｎｔ ｐｒｏｂｌｅｍｓ ｉｎ ｔｈｅｏｒｅｔｉｃａｌ ｃｏｍｐｕｔｅｒ ｓｃｉｅｎｃｅ． Ｂｅｃａｕｓｅ ｔｈｅ ｃｏｎｃｅｐｔｓ ａｂｏｕｔ ｉｔ ａｒｅ ｖｅｒｙ ａｂｓｔｒａｃｔ ａｎｄ ｃｏｍｐｌｉｃａｔｅｄ， ｓｏｍｅ ｓｃｈｏｌａｒｓ ａｎｄ ｓｔｕｄｅｎｔｓ ｉｎ ｃｏｍｐｕｔｅｒ ｓｃｉｅｎｃｅ ｏｆｔｅｎ ｍｉｓｕｎｄｅｒｓｔａｎｄ ｔｈｅｍ． Ａ ｌｏｔ ｏｆ ｐｕｂｌｉｓｈｅｄ ｐａｐｅｒｓ ｃｏｎｔａｉｎ ｔｈｅｓｅ ｍｉｓｕｎｄｅｒｓｔａｎｄｉｎｇｓ． Ｔｈｅ ｍａｉｎ ｐｒｏｂｌｅｍｓ ａｒｅ： ｔｈｅ ｄｅｆａｕｌｔｓ ｉｎ ｕｎｄｅｒｓｔａｎｄｉｎｇ ｔｈｅ ｃｏｎｃｅｐｔｓ ｏｆ ＮＰ ａｎｄ ＮＰＣ， ｕｎｃｌｅａｒｌｙ ｕｎｄｅｒｓｔａｎｄｉｎｇ ｔｈｅ ｃｏｎｃｅｐｔｓ ｏｆ ｄｅｔｅｒｍｉｎｉｓｔｉｃ ｔｕｒｉｎｇ ｍａｃｈｉｎｅ ａｎｄ ｎｏｎ－ｄｅｔｅｒｍｉｎｉｓｔｉｃ ｔｕｒｉｎｇ ｍａｃｈｉｎｅ， ｍｉｓｒｅａｄｉｎｇ ｔｈｅ ｒｅｌａｔｉｏｎｓｈｉｐ ｏｆ Ｐ ａｎｄ ＮＰ ａｎｄ ｍｉｓｌｅａｄｉｎｇ ｉｎ ｔｈｅ ｓｔｕｄｙ ｄｉｒｅｃｔｉｏｎ ｏｆ ＮＰ， ｅｔｃ． Ｏｆ ａｌｌ ｔｈｅｓｅ ｃｏｎｃｅｐｔｓ， ｔｈｅ ｃｏｒｅ ｃｏｎｃｅｐｔ ｉｓ ｔｈｅ ＮＰ－ｃｏｍｐｌｅｔｅ ｐｒｏｂｌｅｍ． Ｉｎ ｔｈｉｓ ｐａｐｅｒ， ｗｅ ａｎａｌｙｚｅｄ ｔｈｅ ｍｉｓｕｎｄｅｒｓｔａｎｄｉｎｇｓ． Ｂｙ ｄｅｅｐｌｙ ｓｔｕｄｙｉｎｇ ｔｈｅ ｄｅｆｉｎｉｔｉｏｎｓ， ｗｅ ｒｅｖｅａｌｅｄ ｔｈｅｉｒ ｅｓｓｅｎｃｅ． Ｓｐｅｃｉａｌｌｙ， ｂｙ ａｎａｌｙｚｉｎｇ ａ ｌｏｔ ｏｆ ｑｕｅｓｔｉｏｎｓ ｉｎ ｄｉｆｆｅｒｅｎｔ ｆｉｅｌｄｓ， ｗｅ ｇａｖｅ ｓｏｍｅ ｈｅｕｒｉｓｔｉｃ ｓｔｒａｉｎ ｏｆ ｔｈｏｕｇｈｔｓ ｆｏｒ ｔｈｅ ｐｏｓｓｉｂｌｅ ｗａｙｓ ｔｏ ｓｏｌｖｅ ｔｈｅ ＮＰ－ｃｏｍｐｌｅｔｅ ｐｒｏｂｌｅｍ ａｎｄ ｔｈｅ ｐｏｓｓｉｂｌｅ ｄｉｒｅｃｔｉｏｎｓ ｔｏ ｓｔｕｄｙ ｉｔ．

参考文献/References:

［１］　ＡＲＯＲＡ Ｓ， ＢＡＲＡＫ Ｂ． Ｃｏｍｐｌｅｘｉｔｙ Ｔｈｅｏｒｙ： Ａ Ｍｏｄｅｒｎ Ａｐｐｒｏａｃｈ Ｃａｍｂｒｉｄｇｅ Ｕｎｉｖｅｒｓｉｔｙ Ｐｒｅｓｓ［Ｍ］．Ｃａｍｂｒｉｄｇｅ，２００９［２］　ＡＡＲＯＮＳＯＮ Ｓ． Ｉｓ Ｐ ｖｅｒｓｕｓ ＮＰ ｆｏｒｍａｌｌｙ ｉｎｄｅｐｅｎｄｅｎｔ［Ｊ］． Ｂｕｌｌｅｔｉｎ ｏｆ ｔｈｅ Ｅｕｒｏｐｅａｎ Ａｓｓｏｃｉａｔｉｏｎ ｆｏｒ Ｔｈｅｏｒｅｔｉｃａｌ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，２００３，８１（１０）：１０９－１３６．［３］　杜丁柱，葛可一，王洁．计算复杂性导引［Ｍ］．北京：高等教育出版社，２００２：３５－５７．ＤＵ ｉｎｇ－ｚｈｕ，Ｇｅ Ｋｅｙｉ，Ｗａｎｇ Ｊｉｅ．Ｉｎｔｒｏｄｕｃｔｉｏｎ ｔｏ Ｃｏｍｐｕｔｉｎｇ Ｃｏｍｐｌｅｘｉｔｙ［Ｍ］．Ｐｅｋｉｎｇ：Ｈｉｇｈ Ｅｄｕｃａｔｉｏｎ Ｐｒｅｓｓ，２００２：３５－５７．（in Chinese）［４］　ＳＡＲＴＡＪ Ｓａｈｎｉ，Ｄａｔａ Ｓｔｒｕｃｔｕｒｅｓ，Ａｌｇｏｒｉｔｈｍｓ，ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ ｉｎ Ｃ＋＋［Ｍ］． ＭｃＧｒａｗ－Ｈｉｌｌ，１９９８． ［５］　ＣＯＯＫ Ｓ Ａ． Ｔｈｅ ｃｏｍｐｌｅｘｉｔｙ ｏｆ ｔｈｅｏｒｅｍ ｐｒｏｖｉｎｇ ｐｒｏｃｅｄｕｒｅｓ［Ｍ］． Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ Ｔｈｉｒｄ Ａｎｎｕａｌ ＡＣＭ Ｓｙｍｐｏｓｉｕｍ， Ｎｅｗ Ｙｏｒｋ： ｏｎ Ｔｈｅｏｒｙ ｏｆ Ｃｏｍｐｕｔｉｎｇ， Ａｓｓｏｃｉａｔｉｏｎ ｆｏｒ Ｃｏｍｐｕｔｉｎｇ Ｍａｃｈｉｎｅｒｙ，１９７１：１５１－１５８．［６］　ＫＡＲＰ Ｒ Ｍ． Ｒｅｄｕｃｉｂｉｌｉｔｙ ａｍｏｎｇ ｃｏｍｂｉｎａｔｏｒｉａｌ ｐｒｏｂｌｅｍｓ［Ｍ］． Ｍｉｌｌｅｒ Ｒ Ｅ， Ｔｈａｔｃｈｅｒ Ｊ Ｗ Ｐｌｅｎｕｍ Ｐｒｅｓｓ， Ｃｏｍｐｌｅｘｉｔｙ ｏｆ Ｃｏｍｐｕｔｅｒ Ｃｏｍｐｕｔａｔｉｏｎｓ，Ｎｅｗ Ｙｏｒｋ：１９７２：８５－１０４．［７］　ＬＡＮＣＥ Ｆｏｒｔｎｏｗ． Ｔｈｅ Ｓｔａｔｕｓ ｏｆ ｔｈｅ Ｐ Ｖｅｒｓｕｓ ＮＰ Ｐｒｏｂｌｅｍ［Ｊ］．Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ｏｆ ｔｈｅ ＡＣＭ，２０１０，５２（９）：７８－８６．［８］　朱丽君， 陈金芳． 大数据下中文期刊论文被引分析［Ｊ］．武汉工程大学学报，２０１５，３７（５）：７４－７８． ＺＨＵ Ｌｉ－ｊｕｎ，ＣＨＥＮ Ｊｉｎ－ｆａｎｇ．Ｃｉｔａｔｉｏｎ ａｎａｌｙｓｉｓ ｏｎ Ｃｈｉｎｅｓｅ Ｐｅｒｉｏｄｉｃａｌｓ Ｕｎｄｅｒ ｂｉｇ ｄａｔａ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｗｕｈａｎ Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ，２０１５，３７（５）：７４－７８．（in Chinese） ［９］　付 敏， 戴祖旭，王道蓬．压缩编码的上下文树构造算法［Ｊ］．武汉工程大学学报，２０１５，３７（４）：５１－５５． Ｆｕ Ｍｉｎ，Ｄａｉ Ｚｕｘｕｅ，ＷＡＮＧ Ｄａｏ－ｐｅｎｇ． Ｃｏｎｔｅｘｔ ｔｒｅｅ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｃｏｍｐｒｅｓｓｉｏｎ ｅｎｃｏｄｉｎｇ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｗｕｈａｎ Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ，２０１５，３７（４）：５１－５５．（in Chinese）［１０］　殷秀叶．大数据环境下的相似重复记录检测方法［Ｊ］．武汉工程大学学报，２０１４，３６（９）：６６－６９． ＹＩＮ Ｘｉｕ ｙｅ．Ｍｅｔｈｏｄ ｆｏｒ ｄｅｔｅｃｔｉｎｇ ａｐｐｒｏｘｉｍａｔｅｌｙ ｄｕｐｌｉｃａｔｅ ｄａｔａｂａｓｅ ｒｅｃｏｒｄｓ ｉｎ ｂｉｇ ｄａｔａ ｅｎｖｉｒｏｎｍｅｎｔ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ Ｗｕｈａｎ Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ，２０１４（９）：６６－６９．（in Chinese）［１１］　ＰＯＳＡ Ｌ． Ｈａｍｉｌｔｏｎｉａｎ ｃｉｒｃｕｉｔｓ ｉｎ ｒａｎｄｏｍ ｇｒａｐｈｓ［Ｊ］． Ｄｉｓｃｒｅｔｅ Ｍａｔｈ，１９７６（１４）：３５９－３６４．

相似文献/References:

备注/Memo

备注/Memo:
收稿日期:2015-08-17基金项目:湖北省自然科学基金项目(2014CFC1121)作者简介:杜立智(1964-),男,湖北黄冈人,副教授,硕士. 研究方向:计算机算法;计算数学;计算复杂性.
更新日期/Last Update: 2015-11-16