P与NP问题研究_杜立智.pdf

《P与NP问题研究_杜立智.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第23卷第1期计算机技术与发展Vol．23No．12013年1月COMPUTERTECHNOLOGYANDDEVELOPMENTJan．2013P与NP问题研究杜立智，符海东，张鸿，黄远林(武汉科技大学计算机科学与技术学院，湖北武汉430065)摘要:P与NP问题被列为七大世界数学难题之首，由于其相关概念抽象而复杂，许多该领域的学生学者，对其相关概念的理解存在谬误，不少已发表的研究论文都体现了这一谬误。用中文通俗讲解到底什么是P和NP问题以及它们的关系，透过抽象的定义揭示其本质。列举一些科研论文上常见的对P和NP问题理解上的谬误，通过分析揭示其错误实质。同时并对解决这一问题可能的研

2、究方法作一综述，对研究前景做一展望，为在该方向上学习和研究的学生学者，提供有价值的参考。由于文中包括:对复杂抽象的概念进行通俗而深入的剖析，对已有的研究进展进行摘要概括，对未来可能的研究方法和研究路线进行综述和分析，故能对该领域的研究者在概念的正确把握、文献的查阅和研究方向的选择上提供助益。关键词:七大数学难题;确定性图灵机;非确定性图灵机;NP完全问题中图分类号:TP31文献标识码:A文章编号:1673－629X(2013)01－0037－06doi:10．3969/j．jssn．1673－629X．2013．01．010AStudyofPvs．NPDULi－zhi，FUHai－

3、dong，ZHANGHong，HUANGYuan－lin(CollegeofComputerScienceandTechn．，WuhanUniversityofScienceandTechn．，Wuhan430065，China)Abstract:PversusNPisthefirstoneofthefamoussevengreatmathematicalproblemsinthisworld．Becausetheconceptsaboutthemareveryabstractandcomplicated，somescholarsandstudentsincomputerscien

4、ceoftenmisunderstandthem．Alotofpublishedpaperscon-tainthesemisunderstandings．ItexplainstheseconceptsinChineseclearly．Bydeeplystudyingtheirdefinitions，revealtheiressence．Listalotofmisunderstandingsoftheseconceptsandanalysethem．Alsosurveytheresearchmethodsandforeseetheresearchfutureofthisfield，s

5、oastogiveanassistancetothisfield＇speople．Itcontains:toanalyzethecomplexandabstractconceptsinaneasyway，topickupimportantpointsfromalotofproducts，tosurveyandanalyzethemethodsforthefuturestudy，soitcanhelptheresearchersinthisfieldforalltheaboveaspects．Keywords:thesevengreatmathematicalproblems;det

6、erministicturingmachines;nondeterministicturingmachines;NPcompleteprob-lems0引言到这样的错误提法:由于某问题是NP问题，故不可能2000年，美国克莱数学研究所公布了世界七大数有多项式时间算法，云云。甚至一些有一定档次的科学难题，又称千禧年大奖难题，规定对每一难题的破解研论文通篇都建立在错误的概念的认识上。者颁发一百万美元的奖金。其中P与NP问题被列为文中的目的是，用中文通俗讲解到底什么是P和这七大数学难题之首，从而大大激发了对这一问题的NP问题以及它们的关系，透过抽象的定义揭示其本研究热情。质。列举一些科研

7、论文上常见的对P和NP问题理解然而，由于P和NP问题及其相关概念相当抽象上的谬误，并通过分析揭示其错误实质。同时对解决而复杂，加之这类问题的原创在国外，一些翻译过来的这一问题可能的研究方法作一综述，对研究前景做一相关书籍往往表达不准确，甚至出现翻译错误，使得许展望，为在该方向上学习和研究的学生学者，提供有价多研究这个问题的中国学者以错误的概念为基础，更值的参考。不谈相关专业的本科生研究生对这些概念缺乏真正准由于文中包括:对复杂抽象的概念进行通俗而深确的理解了。例如，不