算法設(shè)計與分析-05NP完全問題-一些重要的概念

算法設(shè)計與分析——NP完全問題2023/2/41算法設(shè)計與分析演示稿紀(jì)玉波制作(C)一、一些重要的概念

1、多項(xiàng)式時間算法和難解問題不同的算法具有很不相同的時間復(fù)雜性函數(shù)，什么樣的算法算作“效率高”，什么樣的算法算作“效率低”，計算機(jī)科學(xué)家們公認(rèn)一種簡單的區(qū)別，這就是多頂式時間算法（polynomialtimealgorithm)和指數(shù)時間算法（exponentialtimealgorithm)之間的區(qū)別。Cobham[1964］和Edmonds[1965］首先討論了這種區(qū)別的基本性質(zhì)。特別是Edmonds把多項(xiàng)式時間算法與“好的”算法等同看待，并且猜想某些整數(shù)規(guī)劃問題可能不能用這種“好的”算法求解。這反映了一種觀點(diǎn)，認(rèn)為指數(shù)時間算法不應(yīng)該算作“好的”算法。通常也的確是這樣的。大多數(shù)指數(shù)時間算法只是窮舉搜索法的變種，而多項(xiàng)式時間算法通常只有在對問題的結(jié)構(gòu)有了某些比較深入的了解之后才有可能給出。艱多人都認(rèn)為只有知道了問題的多項(xiàng)式時間算法才能認(rèn)為“很好地解決了”這個問題。因此，如果一個問題困難到不可能用多項(xiàng)式時間算法求解，那末我們就認(rèn)為這個問題是“難解的”。2023/2/42算法設(shè)計與分析演示稿紀(jì)玉波制作(C)不過，有些指數(shù)時間算法在實(shí)際中可能十分有用。作為定義，時間復(fù)雜性是一種最壞情況的度量。時間復(fù)雜性為2n的算法僅僅表示至少有一個規(guī)模為n的問題實(shí)例需要這么多的運(yùn)算時間，而大多數(shù)問題實(shí)例可能實(shí)際上需要遠(yuǎn)比這個少得多的時間。有幾個著名的算法就是這種情況。已經(jīng)證明線性規(guī)劃的單純形算法具有指數(shù)時間復(fù)雜性[KleeandMinty，1972］，但是在實(shí)際中它計算得很好，給人留下了深刻印象。同樣，背包問題的分支界限算法雖然也具有指數(shù)時間復(fù)雜性，但是它是一種非常成功的算法，使得許多人認(rèn)為背包問題已經(jīng)很好地解決了。2023/2/43算法設(shè)計與分析演示稿紀(jì)玉波制作(C)遺憾的是，像這樣的例子太少了。雖然對于很多問題都知道指數(shù)時間算法，但是只有少數(shù)幾個被認(rèn)為在實(shí)際中是很有用的。甚至上面提到的那幾個成功的指數(shù)時間算法也沒有使研究人員停止繼續(xù)尋找這些問題的多項(xiàng)式時間算法的努力。實(shí)際上，這些算法的真正成功產(chǎn)生了一種猜疑，認(rèn)為它們不知怎么地抓住了這些問題的關(guān)鍵性的性質(zhì)，對這些性質(zhì)的仔細(xì)研究可能給出更好的方法，至今在解釋這種成功方面幾乎毫無進(jìn)展，也沒有一種方法能夠事先預(yù)言給定的指數(shù)時間算法在實(shí)際中能否快速運(yùn)算。2023/2/44算法設(shè)計與分析演示稿紀(jì)玉波制作(C)另一方面，如果多項(xiàng)式時間算法滿足對運(yùn)算時間更嚴(yán)格得多的限制，就往往可以作出這種預(yù)言。雖然可以認(rèn)為時間復(fù)雜性為n100或1099n2的算法在實(shí)際中不大可能快速運(yùn)算，但是自然提出的多項(xiàng)式可解的問題大多數(shù)可用2次，或者在最壞的情況下用3次多項(xiàng)式時間算法求解，而且在多項(xiàng)式中不包含特別大的系數(shù)，可以認(rèn)為滿足這些限制的算法是“可證地有效”算法。正是這種特別需要的性質(zhì)使我們優(yōu)先考慮用多項(xiàng)式時間算法解決問題。2023/2/45算法設(shè)計與分析演示稿紀(jì)玉波制作(C)關(guān)于計算機(jī)模型的選擇可以作類似的注釋。至今研究過的所有實(shí)際的計算機(jī)模型，例如單帶圖靈機(jī)，多帶圖靈機(jī)以及隨機(jī)存取機(jī)（RAM）都是相對于多項(xiàng)式時間復(fù)雜性等價的，人們可以指望任何其它“合理的”模型都享有這種等價性。這里所說的“合理的”概念在本質(zhì)上是指在單位時間內(nèi)可以完成的工作量有一個多項(xiàng)式界限。例如，不能認(rèn)為具有完成任意多道并行運(yùn)算能力的模型是“合理的“，而且也確實(shí)不存在一合計算機(jī)具有這種能力。無論如何，只要我們規(guī)定只采用實(shí)際的計算機(jī)標(biāo)準(zhǔn)模型，難解的問題類就不受使用的具體模型的影響。因而我們可以根據(jù)方便與否來選擇計算機(jī)模型，而不會妨礙結(jié)果的使用?！昂侠淼摹庇嬎銠C(jī)模型也稱為是“確定型”（deterministic)的計算機(jī)模型。2023/2/46算法設(shè)計與分析演示稿紀(jì)玉波制作(C)這樣一來，“難解的”定義在理論上給出了重要的一般原則。即問題的難度在本質(zhì)上不依賴于用來決定時間復(fù)雜性的具體編碼方案和計算機(jī)模型。

能夠用實(shí)際的計算機(jī)標(biāo)準(zhǔn)模型在多項(xiàng)式時間算法（Polynomialtimealgorithm)內(nèi)求解的問題稱為P類問題。2023/2/47算法設(shè)計與分析演示稿紀(jì)玉波制作(C)2、可證的難解問題最早證出的難解性問題結(jié)果是經(jīng)典的圖靈不可判定性。四十多年前，圖靈證明某些問題困難到“不可判定的”程度，即根本不可能給出解這些問題的算法。例如，他證明不可能給出一個算法，當(dāng)任意給定一個計算機(jī)程序和這個程序的輸入時，該算法可以判定當(dāng)把這個程序應(yīng)用于這個輸入時最終是否停機(jī)[Turing，1936]?，F(xiàn)在已經(jīng)知道還有各種其它問題也是不可判定的，這些問題包括有限表示群的平凡問題[Rabin，1958]，希爾伯特第十問題（整數(shù)多項(xiàng)式的可解性）[Matijasevic，1970］等。因?yàn)椴豢赡苡萌魏嗡惴?，?dāng)然更不可能用多項(xiàng)式時間算法解這些不可判定問題，所以它們的確是在特別強(qiáng)的意義下難解的。2023/2/48算法設(shè)計與分析演示稿紀(jì)玉波制作(C)

第一個難解的“可判定”問題是在六十年代初獲得的，它是Hartmanis和Stearns［1965]的復(fù)雜性“譜系”工作的一部分，但是，這些結(jié)果只包括一些“人工制造的”問題，它們被專門構(gòu)造成具有所需要的性質(zhì)。直到七十年代初，Meyer和Stockmeyer[1972］，F(xiàn)ischer和Rabin［1974］以及其他人終于成功地證明某些“自然的”可判定問題是難解的，這些問題包括自動機(jī)理論、形式語言理論以及數(shù)理邏輯中以前研究過的各種問題。實(shí)際上，他們的證明表明甚至用“非確定型”（nondeterministic)計算機(jī)模型也不可能在多項(xiàng)式時間內(nèi)解這些問題，這種“非確定型”計算機(jī)模型具有執(zhí)行無限多個獨(dú)立的并行計算序列的能力。這種“不合理的”計算機(jī)模型在NP完全性理論中起著重要的作用。2023/2/49算法設(shè)計與分析演示稿紀(jì)玉波制作(C)

迄今為止我們已經(jīng)知道的所有可證的難解問題分成剛才敘述的兩種類型，它們或者是“不可判定的”，或者是“非確定型”難解的。但是，大多數(shù)在實(shí)際中遇到的在表面上看來難解的問題是可判定的，并且可以用非確定型計算機(jī)在多項(xiàng)式時間內(nèi)求解。因此，要證明這些問題的表面上的難解性，至今所研究過的證明方法都還不夠有力。2023/2/410算法設(shè)計與分析演示稿紀(jì)玉波制作(C)3、NP完全問題可以用“非確定型”計算機(jī)通過多項(xiàng)式時間算法求解的問題稱為“NP類”問題。理論工作者們一方面繼續(xù)尋找更有力的方法來證明問題的難解性，同時又在努力研究就難度而言各種問題相互聯(lián)系的方式。發(fā)現(xiàn)問題之間的這種相互聯(lián)系常常可以給算法設(shè)計人員提供有用的信息。證明兩個問題相關(guān)的基本方法是通過給出一個構(gòu)造性變換把第一個問題的任一實(shí)例映射到第二個問題的一個等價的實(shí)例，從而把第一個問題“歸約”為第二個問題。這樣的變換提供了一個手段，把解第二個問題的任何算法轉(zhuǎn)變成解第一個問題的相應(yīng)的算法。2023/2/411算法設(shè)計與分析演示稿紀(jì)玉波制作(C)早期就找到了許多這種簡單的歸約。例如，Dantzig［1960］把一些組合最優(yōu)化問題歸約為一般的0-l整數(shù)線性規(guī)劃問題，Edmonds［1962］把圖論問題“用最少的頂點(diǎn)覆蓋所有邊”和“尋找最大的頂點(diǎn)獨(dú)立集”歸約為一般的“集合覆蓋問題”。Gimple［1965］把一般的集合覆蓋問題歸約為邏輯設(shè)計的“素蘊(yùn)涵覆蓋問題”，Dantzig，Blattner和Rao[1966]描述了一個“著名的”歸約，把巡回推銷員問題歸約為帶非負(fù)邊長的“最短路徑問題”。2023/2/412算法設(shè)計與分析演示稿紀(jì)玉波制作(C)StephenCook于1971年發(fā)表的題為“定理證明過程的復(fù)雜性”一文奠定了NP完全性理論的基礎(chǔ)。在這篇簡潔而又精致的文章中Cook做了幾件重要的事情。第一，他強(qiáng)調(diào)了“多項(xiàng)式時間可歸約性”的重要意義，所謂多項(xiàng)式時間歸約是指可以用多項(xiàng)式時間算法實(shí)現(xiàn)所需要的變換的歸約。如果我們有從第一個問題到第二個問題的多項(xiàng)式時間歸約，那末就一定能把第二個問題的任何多項(xiàng)式時間算法轉(zhuǎn)換成第一個問題的多項(xiàng)式時間算法。第二，他把注意力集中在判定向題的NP類上，這類問題可以用非確定型計算機(jī)在多項(xiàng)式時間內(nèi)解決。（如果問題的解不是“是”就是“否”，則稱這個問題是判定向題。）在實(shí)際中遇到的表面上看來難解的問題，當(dāng)把它們表成判定問題時，大多數(shù)屬于這一類。2023/2/413算法設(shè)計與分析演示稿紀(jì)玉波制作(C)第三，他證明了NP中的一個名叫“可滿足性”問題的具體問題具有這樣的性質(zhì)：NP類中的所有其它問題都可以多項(xiàng)式歸約為這個問題。如果可滿足性問題可以用多項(xiàng)式時間算法解決，那末NP類中的所有問題也都可以用多項(xiàng)式時間算法解決。如果NP中的某個問題是難解的，那末可滿足性問題也一定是難解的。因此，在某種意義下，可滿足性問題是NP類中“最難的”問題。最后，Cook認(rèn)為NP類中的一些其它問題可能和可滿足性問題一樣，具有這種成為NP類中“最難的”問題的性質(zhì)。他證明對于問題“給定的圖G是否包含k個頂點(diǎn)上的完全子圖？其中k是給定的自然數(shù)”就是這種清況。2023/2/414算法設(shè)計與分析演示稿紀(jì)玉波制作(C)隨后，RichardKarp給出了一組結(jié)果［1972]，證明許多著名的組合問題,包括巡回推銷員問題在內(nèi)的判定問題形式確實(shí)恰好與可滿足性問題一樣難。從那以后證明了各種各樣的其它問題在難度上等價于這些問題，這些問題構(gòu)成了一個NP等價問題(NPequivalentproblem)類，并給這個等價類起了一個名字，叫做NP完全問題(NPcompleteproblem)類，它是由NP中所有“最難的”問題組成。已經(jīng)證明Cook的原始思想是相當(dāng)有力的。它提供了一些方法把許多個別的復(fù)雜性問題聯(lián)合成一個問題：NP完全問題是難解的嗎？由于越來越多的具有獨(dú)立意義的問題被證明屬于這個等價類，所以它的重要性還在繼續(xù)增長。2023/2/415算法設(shè)計與分析演示稿紀(jì)玉波制作(C)現(xiàn)在認(rèn)為NP完全問題是否是難解的這一向題是當(dāng)代數(shù)學(xué)和計算機(jī)科學(xué)中尚未解決的最重要問題之一。盡管大多數(shù)研究工作者猜想NP完全問題是難解的，然而在證明或否定這個廣泛的猜想方面幾乎沒有取得什么進(jìn)展。但是，即使沒有證明NP完全性蘊(yùn)涵難解性，知道一個問題是NP完全的至少暗示著要想用多項(xiàng)式時間算法解這個問題必須有重大的突破。2023/2/416算法設(shè)計與分析演示稿紀(jì)玉波制作(C)實(shí)用中，知道一個問題是NP完全的就給我們提供了有價值的信息，告訴我們采用什么樣的途徑可以是最富有成效的。一定不要去優(yōu)先尋找有效的、精確的算法。現(xiàn)在比較適當(dāng)?shù)耐緩绞羌芯χ铝τ谄渌^低目標(biāo)的方法。例如，你可以尋找解決這個問題的各種特殊情況的有效算法。尋找在大多數(shù)情況下看來能快速運(yùn)算的算法，雖然不能保證它在任何情況下都能快速地運(yùn)算?；蛘吣?/p>