資源描述：
《P與NP問題研究_杜立智.pdf》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、第23卷第1期計算機技術(shù)與發(fā)展Vol．23No．12013年1月COMPUTERTECHNOLOGYANDDEVELOPMENTJan．2013P與NP問題研究杜立智，符海東，張鴻，黃遠林(武漢科技大學(xué)計算機科學(xué)與技術(shù)學(xué)院，湖北武漢430065)摘要:P與NP問題被列為七大世界數(shù)學(xué)難題之首，由于其相關(guān)概念抽象而復(fù)雜，許多該領(lǐng)域的學(xué)生學(xué)者，對其相關(guān)概念的理解存在謬誤，不少已發(fā)表的研究論文都體現(xiàn)了這一謬誤。用中文通俗講解到底什么是P和NP問題以及它們的關(guān)系，透過抽象的定義揭示其本質(zhì)。列舉一些科研論文上常見的對P和NP問題理解上的謬誤，通過分析揭示其錯誤實質(zhì)。同時并對解決這一問題可能的研
2、究方法作一綜述，對研究前景做一展望，為在該方向上學(xué)習(xí)和研究的學(xué)生學(xué)者，提供有價值的參考。由于文中包括:對復(fù)雜抽象的概念進行通俗而深入的剖析，對已有的研究進展進行摘要概括，對未來可能的研究方法和研究路線進行綜述和分析，故能對該領(lǐng)域的研究者在概念的正確把握、文獻的查閱和研究方向的選擇上提供助益。關(guān)鍵詞:七大數(shù)學(xué)難題;確定性圖靈機;非確定性圖靈機;NP完全問題中圖分類號:TP31文獻標(biāo)識碼:A文章編號:1673－629X(2013)01－0037－06doi:10．3969/j．jssn．1673－629X．2013．01．010AStudyofPvs．NPDULi－zhi，F(xiàn)UHai－
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年，美國克萊數(shù)學(xué)研究所公布了世界七大數(shù)有多項式時間算法，云云。甚至一些有一定檔次的科學(xué)難題，又稱千禧年大獎難題，規(guī)定對每一難題的破解研論文通篇都建立在錯誤的概念的認識上。者頒發(fā)一百萬美元的獎金。其中P與NP問題被列為文中的目的是，用中文通俗講解到底什么是P和這七大數(shù)學(xué)難題之首，從而大大激發(fā)了對這一問題的NP問題以及它們的關(guān)系，透過抽象的定義揭示其本研究熱情。質(zhì)。列舉一些科研
7、論文上常見的對P和NP問題理解然而，由于P和NP問題及其相關(guān)概念相當(dāng)抽象上的謬誤，并通過分析揭示其錯誤實質(zhì)。同時對解決而復(fù)雜，加之這類問題的原創(chuàng)在國外，一些翻譯過來的這一問題可能的研究方法作一綜述，對研究前景做一相關(guān)書籍往往表達不準確，甚至出現(xiàn)翻譯錯誤，使得許展望，為在該方向上學(xué)習(xí)和研究的學(xué)生學(xué)者，提供有價多研究這個問題的中國學(xué)者以錯誤的概念為基礎(chǔ)，更值的參考。不談相關(guān)專業(yè)的本科生研究生對這些概念缺乏真正準由于文中包括:對復(fù)雜抽象的概念進行通俗而深確的理解了。例如，不
