參考資料NP完全問(wèn)題-一些重要的概念.ppt

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

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

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

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

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

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

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

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

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

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

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

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

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