1、2020/9/13,1,NP完全問題,2020/9/13,2,一、一些重要的概念1、多項式時間算法和難解問題,不同的算法具有很不相同的時間復(fù)雜性函數(shù)，什么樣的算法算作“效率高”，什么樣的算法算作“效率低”，計算機科學(xué)家們公認(rèn)一種簡單的區(qū)別，這就是多頂式時間算法（polynomial time algorithm)和指數(shù)時間算法（exponential time algorithm)之間的區(qū)別。Cobham1964和Edmonds1965首先討論了這種區(qū)別的基本性質(zhì)。特別是Edmonds把多項式時間算法與“好的”算法等同看待，并且猜想某些整數(shù)規(guī)劃問題可能不能用這種“好的”算法求解。這反映了一種觀

2、點，認(rèn)為指數(shù)時間算法不應(yīng)該算作“好的”算法。通常也的確是這樣的。大多數(shù)指數(shù)時間算法只是窮舉搜索法的變種，而多項式時間算法通常只有在對問題的結(jié)構(gòu)有了某些比較深入的了解之后才有可能給出。艱多人都認(rèn)為只有知道了問題的多項式時間算法才能認(rèn)為“很好地解決了”這個問題。因此，如果一個問題困難到不可能用多項式時間算法求解，那末我們就認(rèn)為這個問題是“難解的”。,2020/9/13,3,不過，有些指數(shù)時間算法在實際中可能十分有用。作為定義，時間復(fù)雜性是一種最壞情況的度量。時間復(fù)雜性為2n的算法僅僅表示至少有一個規(guī)模為n的問題實例需要這么多的運算時間，而大多數(shù)問題實例可能實際上需要遠(yuǎn)比這個少得多的時間。有幾個著名

3、的算法就是這種情況。已經(jīng)證明線性規(guī)劃的單純形算法具有指數(shù)時間復(fù)雜性Klee and Minty，1972，但是在實際中它計算得很好，給人留下了深刻印象。同樣，背包問題的分支界限算法雖然也具有指數(shù)時間復(fù)雜性，但是它是一種非常成功的算法，使得許多人認(rèn)為背包問題已經(jīng)很好地解決了。,2020/9/13,4,遺憾的是，像這樣的例子太少了。雖然對于很多問題都知道指數(shù)時間算法，但是只有少數(shù)幾個被認(rèn)為在實際中是很有用的。甚至上面提到的那幾個成功的指數(shù)時間算法也沒有使研究人員停止繼續(xù)尋找這些問題的多項式時間算法的努力。實際上，這些算法的真正成功產(chǎn)生了一種猜疑，認(rèn)為它們不知怎么地抓住了這些問題的關(guān)鍵性的性質(zhì)，對這

4、些性質(zhì)的仔細(xì)研究可能給出更好的方法，至今在解釋這種成功方面幾乎毫無進展，也沒有一種方法能夠事先預(yù)言給定的指數(shù)時間算法在實際中能否快速運算。,2020/9/13,5,另一方面，如果多項式時間算法滿足對運算時間更嚴(yán)格得多的限制，就往往可以作出這種預(yù)言。雖然可以認(rèn)為時間復(fù)雜性為n100或1099n2的算法在實際中不大可能快速運算，但是自然提出的多項式可解的問題大多數(shù)可用2次，或者在最壞的情況下用3次多項式時間算法求解，而且在多項式中不包含特別大的系數(shù)，可以認(rèn)為滿足這些限制的算法是“可證地有效”算法。正是這種特別需要的性質(zhì)使我們優(yōu)先考慮用多項式時間算法解決問題。,2020/9/13,6,關(guān)于計算機模型

5、的選擇可以作類似的注釋。至今研究過的所有實際的計算機模型，例如單帶圖靈機，多帶圖靈機以及隨機存取機（RAM）都是相對于多項式時間復(fù)雜性等價的，人們可以指望任何其它“合理的”模型都享有這種等價性。這里所說的“合理的”概念在本質(zhì)上是指在單位時間內(nèi)可以完成的工作量有一個多項式界限。例如，不能認(rèn)為具有完成任意多道并行運算能力的模型是“合理的“，而且也確實不存在一合計算機具有這種能力。無論如何，只要我們規(guī)定只采用實際的計算機標(biāo)準(zhǔn)模型，難解的問題類就不受使用的具體模型的影響。因而我們可以根據(jù)方便與否來選擇計算機模型，而不會妨礙結(jié)果的使用。 “合理的”計算機模型也稱為是“確定型”（deterministic

6、)的計算機模型。,2020/9/13,7,這樣一來，“難解的”定義在理論上給出了重要的一般原則。即問題的難度在本質(zhì)上不依賴于用來決定時間復(fù)雜性的具體編碼方案和計算機模型。 能夠用實際的計算機標(biāo)準(zhǔn)模型在多項式時間算法（Polynomial time algorithm)內(nèi)求解的問題稱為P類問題。,2020/9/13,8,2、可證的難解問題,最早證出的難解性問題結(jié)果是經(jīng)典的圖靈不可判定性。四十多年前，圖靈證明某些問題困難到“不可判定的”程度，即根本不可能給出解這些問題的算法。例如，他證明不可能給出一個算法，當(dāng)任意給定一個計算機程序和這個程序的輸入時，該算法可以判定當(dāng)把這個程序應(yīng)用于這個輸入時最終是

7、否停機Turing，1936?，F(xiàn)在已經(jīng)知道還有各種其它問題也是不可判定的，這些問題包括有限表示群的平凡問題Rabin，1958，希爾伯特第十問題（整數(shù)多項式的可解性） Matijasevic，1970等。因為不可能用任何算法，當(dāng)然更不可能用多項式時間算法解這些不可判定問題，所以它們的確是在特別強的意義下難解的。,2020/9/13,9,第一個難解的“可判定”問題是在六十年代初獲得的，它是Hartmanis和Stearns1965的復(fù)雜性“譜系”工作的一部分，但是，這些結(jié)果只包括一些“人工制造的”問題，它們被專門構(gòu)造成具有所需要的性質(zhì)。直到七十年代初，Meyer和Stockmeyer1972，F(xiàn)

8、ischer和Rabin1974以及其他人終于成功地證明某些“自然的”可判定問題是難解的，這些問題包括自動機理論、形式語言理論以及數(shù)理邏輯中以前研究過的各種問題。實際上，他們的證明表明甚至用“非確定型”（nondeterministic)計算機模型也不可能在多項式時間內(nèi)解這些問題，這種“非確定型”計算機模型具有執(zhí)行無限多個獨立的并行計算序列的能力。這種“不合理的”計算機模型在NP完全性理論中起著重要的作用。,2020/9/13,10,迄今為止我們已經(jīng)知道的所有可證的難解問題分成剛才敘述的兩種類型，它們或者是“不可判定的”，或者是“非確定型”難解的。但是，大多數(shù)在實際中遇到的在表面上看來難解的問

9、題是可判定的，并且可以用非確定型計算機在多項式時間內(nèi)求解。因此，要證明這些問題的表面上的難解性，至今所研究過的證明方法都還不夠有力。,2020/9/13,11,3、NP完全問題,可以用“非確定型”計算機通過多項式時間算法求解的問題稱為“NP類”問題。理論工作者們一方面繼續(xù)尋找更有力的方法來證明問題的難解性，同時又在努力研究就難度而言各種問題相互聯(lián)系的方式。發(fā)現(xiàn)問題之間的這種相互聯(lián)系常?？梢越o算法設(shè)計人員提供有用的信息。證明兩個問題相關(guān)的基本方法是通過給出一個構(gòu)造性變換把第一個問題的任一實例映射到第二個問題的一個等價的實例，從而把第一個問題“歸約”為第二個問題。這樣的變換提供了一個手段，把解第二

10、個問題的任何算法轉(zhuǎn)變成解第一個問題的相應(yīng)的算法。,2020/9/13,12,早期就找到了許多這種簡單的歸約。例如，Dantzig1960把一些組合最優(yōu)化問題歸約為一般的0-l整數(shù)線性規(guī)劃問題，Edmonds1962把圖論問題“用最少的頂點覆蓋所有邊”和“尋找最大的頂點獨立集”歸約為一般的“集合覆蓋問題”。Gimple1965把一般的集合覆蓋問題歸約為邏輯設(shè)計的“素蘊涵覆蓋問題”，Dantzig，Blattner和Rao1966描述了一個“著名的”歸約，把巡回推銷員問題歸約為帶非負(fù)邊長的“最短路徑問題”。,2020/9/13,13,Stephen Cook于1971年發(fā)表的題為“定理證明過程的復(fù)

11、雜性”一文奠定了NP完全性理論的基礎(chǔ)。在這篇簡潔而又精致的文章中Cook做了幾件重要的事情。 第一，他強調(diào)了“多項式時間可歸約性”的重要意義，所謂多項式時間歸約是指可以用多項式時間算法實現(xiàn)所需要的變換的歸約。如果我們有從第一個問題到第二個問題的多項式時間歸約，那末就一定能把第二個問題的任何多項式時間算法轉(zhuǎn)換成第一個問題的多項式時間算法。 第二，他把注意力集中在判定向題的NP類上，這類問題可以用非確定型計算機在多項式時間內(nèi)解決。（如果問題的解不是“是”就是“否”，則稱這個問題是判定向題。）在實際中遇到的表面上看來難解的問題，當(dāng)把它們表成判定問題時，大多數(shù)屬于這一類。,2020/9/13,14,第

12、三，他證明了NP中的一個名叫“可滿足性”問題的具體問題具有這樣的性質(zhì)：NP類中的所有其它問題都可以多項式歸約為這個問題。如果可滿足性問題可以用多項式時間算法解決，那末NP類中的所有問題也都可以用多項式時間算法解決。如果NP中的某個問題是難解的，那末可滿足性問題也一定是難解的。因此，在某種意義下，可滿足性問題是NP類中“最難的”問題。 最后，Cook認(rèn)為NP類中的一些其它問題可能和可滿足性問題一樣，具有這種成為NP類中“最難的”問題的性質(zhì)。他證明對于問題“給定的圖G是否包含k個頂點上的完全子圖？其中k 是給定的自然數(shù)”就是這種清況。,2020/9/13,15,隨后，Richard Karp給出了

13、一組結(jié)果1972，證明許多著名的組合問題,包括巡回推銷員問題在內(nèi)的判定問題形式確實恰好與可滿足性問題一樣難。從那以后證明了各種各樣的其它問題在難度上等價于這些問題，這些問題構(gòu)成了一個NP等價問題(NP equivalent problem)類 ，并給這個等價類起了一個名字，叫做NP完全問題(NP complete problem)類，它是由NP中所有“最難的”問題組成。 已經(jīng)證明Cook的原始思想是相當(dāng)有力的。它提供了一些方法把許多個別的復(fù)雜性問題聯(lián)合成一個問題：NP完全問題是難解的嗎？由于越來越多的具有獨立意義的問題被證明屬于這個等價類，所以它的重要性還在繼續(xù)增長。,2020/9/13,16,現(xiàn)在認(rèn)為NP完全問題是否是難解的這一向題是當(dāng)代數(shù)學(xué)和計算機科學(xué)中尚未解決的最重要問題之一。盡管大多數(shù)研究工作者猜想NP完全問題是難解的，然而在證明或否定這個廣泛的猜想方面幾乎沒有取得什么進展。但是，即使沒有證明NP完全性蘊涵難解性，知道一個問題是NP完全的至少暗示著要想用多項式時間算法解這個問題必須有重大的突破。,2020/9/13,17,實用中，知道一個問題是NP完全的就給我們提供了有價值的信息，告訴我們采用什么樣的途徑可以是最富有成效的。一定不要去優(yōu)先尋找有效的、精確的算法。現(xiàn)在比較適當(dāng)?shù)耐緩绞羌芯χ铝τ谄渌^低目標(biāo)的方法。例如，你可以尋找解決這個問題的各種特殊情況的有效算法。尋