NP=?P（即NP是否等于P）的問(wèn)題是計(jì)算機(jī)科學(xué)和數(shù)學(xué)中的重要問(wèn)題。美國(guó)克雷數(shù)學(xué)研究院將其列為新千年七大困難問(wèn)題之首,2005年Science將其列為25個(gè)困難問(wèn)題之19。Science最近列出的125個(gè)亟待解決的重要問(wèn)題中,第19個(gè)問(wèn)題實(shí)質(zhì)上就是NP=?P的問(wèn)題。如果NP=P,對(duì)于很多困擾科學(xué)研究的困難計(jì)算問(wèn)題,理論上就存在多項(xiàng)式時(shí)間算法來(lái)迅速求解它們。而現(xiàn)代密碼學(xué)建立在NP≠P的假設(shè)之上。人們希望存在難解問(wèn)題,希望基于難解問(wèn)題構(gòu)造加密算法,希望能夠利用難解問(wèn)題的求解復(fù)雜性對(duì)抗分析和攻擊。如果NP=P,所有在NP≠P假定之上開(kāi)展的計(jì)算研究都至少需要重新審視其意義。NP完全問(wèn)題的求解復(fù)雜性決定NP=P是否成立。針對(duì)一個(gè)被稱(chēng)為MSP問(wèn)題的新問(wèn)題,文中提出了一個(gè)關(guān)于MSP問(wèn)題的多項(xiàng)式時(shí)間算法,并給出了該算法的證明和時(shí)間復(fù)雜性分析。由于已經(jīng)發(fā)表了十多個(gè)經(jīng)典的NP完全問(wèn)題到MSP問(wèn)題的歸結(jié)以及MSP問(wèn)題到SAT問(wèn)題的歸結(jié),因此MSP問(wèn)題存在多項(xiàng)式時(shí)間算法這樣一個(gè)研究結(jié)果對(duì)于研究NP=P有重要和積極的意義。 

【文章頁(yè)數(shù)】：13 頁(yè)

【文章目錄】：
1 問(wèn)題的引入及若干定義
2 求解MSP問(wèn)題的ZH算法
    2.1 4個(gè)基本算子的定義
    2.2 ZH算法的復(fù)雜性分析和必要性證明
    2.3 充分性證明準(zhǔn)備
        2.3.1 兩個(gè)函數(shù)的定義
        2.3.2 構(gòu)造證明框架
    2.4 αβ定理及其證明
    2.5 ZH算法的充分性證明
3 MSP∈NPC的證明以及本文結(jié)論


【參考文獻(xiàn)】：
期刊論文
[1]MSP問(wèn)題的一個(gè)求解算法[J]. 姜新文,吳添君,李鵬坤,樊碩,周泰楊,魏登萍.  計(jì)算技術(shù)與自動(dòng)化. 2016(01)
[2]Z-H算法正確性證明第四次改寫(xiě)[J]. 姜新文,王琪,姜子恒.  計(jì)算技術(shù)與自動(dòng)化. 2010(03)
[3]用轉(zhuǎn)換成多級(jí)圖的方法判定圖的H性質(zhì)[J]. 姜新文.  計(jì)算技術(shù)與自動(dòng)化. 2004(02)



本文編號(hào)：3697614