圖論中P、NP、NPC和NP難問題詳解

1、P問題NP問題NPC問題NP難問題詳解ContentsP問題問題1NP問題問題2NPC問題問題3NP難問題難問題4 時間復(fù)雜度并不是表示一個程序解決問題需要花多少時間，而是當(dāng)問題規(guī)模擴大后，程序需要的時間長度增長得有多快。 不管數(shù)據(jù)有多大，程序處理花的時間始終是那么多的，我們就說這個程序很好，具有O(1)的時間復(fù)雜度，也稱常數(shù)級復(fù)雜度；數(shù)據(jù)規(guī)模變得有多大，花的時間也跟著變得有多長，這個程序的時間復(fù)雜度就是O(n)。時間復(fù)雜度時間復(fù)雜度多項式級的復(fù)雜度 。如 O(1), O(log(n),O(na)等 因為它的規(guī)模n出現(xiàn)在底數(shù)的位置 ！時間復(fù)雜度時間復(fù)雜度非多項式級的 如：O(an)和O(n!)

2、等！ P問題是可以在多項式時間內(nèi)被確定機(通常意義的計算機)解決的問題. 如果一個問題可以找到一個能在多項式的時間里解決它的算法，那么這個問題就屬于P問題。 我們常見到的一些信息奧賽的題目都是P問題。 P問題問題 VS NP問題問題 ？P (Polynomial,多項式)問題NP(Non-Deterministic Polynomial, 非確定多項式)問題 首先：首先：NP問題不是非問題不是非P類問題類問題 ！ NP問題問題,是指可以在多項式時間內(nèi)被非確定機是指可以在多項式時間內(nèi)被非確定機(他可以猜他可以猜,他總是能猜到最能滿足他總是能猜到最能滿足你需要的那種選擇你需要的那種選擇,如果你讓他

3、解決如果你讓他解決n皇后問題皇后問題,他只要猜他只要猜n次就能完成次就能完成-每次都每次都是那么幸運是那么幸運)解決的問題解決的問題.這里有一個著名的問題這里有一個著名的問題-千禧難題之首千禧難題之首,是說是說P問題是問題是否等于否等于NP問題問題,也即是否所有在非確定機上多項式可解的問題都能在確定機上也即是否所有在非確定機上多項式可解的問題都能在確定機上用多項式時間求解用多項式時間求解. NP問題是指可以在多項式的時間里驗證一個解的問題，即可以在多項式的時問題是指可以在多項式的時間里驗證一個解的問題，即可以在多項式的時間里猜出一個解的問題。間里猜出一個解的問題。 像像Hamilton回路問題

4、?；芈穯栴}。 在這個題中，找一個解很困難，但驗證一個解很容易。在這個題中，找一個解很困難，但驗證一個解很容易。 當(dāng)然有不是當(dāng)然有不是NP問題的問題，即咱猜到了解但是沒用，因為咱不能在多項式的問題的問題，即咱猜到了解但是沒用，因為咱不能在多項式的時間里去驗證它。時間里去驗證它。 如下面這個：如下面這個： 我們已經(jīng)知道我們已經(jīng)知道Hamilton回路是回路是NP問題，因為驗證一條路是否恰好經(jīng)過了每問題，因為驗證一條路是否恰好經(jīng)過了每一個頂點非常容易。但我們把問題換成這樣：試問一個圖中是否不存在一個頂點非常容易。但我們把問題換成這樣：試問一個圖中是否不存在Hamilton回路。這樣問題就沒法在多項式

5、的時間里進(jìn)行驗證了，因為除非你試回路。這樣問題就沒法在多項式的時間里進(jìn)行驗證了，因為除非你試過所有的路，否則你不敢斷定它過所有的路，否則你不敢斷定它“沒有沒有Hamilton回路回路”。 已經(jīng)知道所有的已經(jīng)知道所有的P類問題都是類問題都是NP問題。問題。 那反之呢？其實就一句話：證明或那反之呢？其實就一句話：證明或推翻推翻P=NP 這就是所謂的這就是所謂的“NP問題問題”！P問題與問題與NP問題的對比問題的對比 換一種說法換一種說法,如果一個問題的復(fù)雜度是該問題的一個實例規(guī)模如果一個問題的復(fù)雜度是該問題的一個實例規(guī)模n的多項式的多項式函數(shù)，則這種可以在多項式時間內(nèi)解決的問題屬于函數(shù)，則這種可以

6、在多項式時間內(nèi)解決的問題屬于P類問題類問題.通俗地稱所有復(fù)通俗地稱所有復(fù)雜度為多項式時間的問題為易解的問題類，否則為難解的問題。雜度為多項式時間的問題為易解的問題類，否則為難解的問題。有些問題很難找到多項式時間的算法（或許根本不存在），例如有些問題很難找到多項式時間的算法（或許根本不存在），例如“找出找出無向圖中哈密頓回路無向圖中哈密頓回路”問題。但如果給了該問題的一個答案，可以在多項式問題。但如果給了該問題的一個答案，可以在多項式時間內(nèi)判斷這個答案是否正確。例如說對于哈密頓回路問題，給一個任意的時間內(nèi)判斷這個答案是否正確。例如說對于哈密頓回路問題，給一個任意的回路，很容易判斷它是否是哈密頓回

7、路（只要看是不是所有的頂點都在回路回路，很容易判斷它是否是哈密頓回路（只要看是不是所有的頂點都在回路中就可以了）。這里給出中就可以了）。這里給出NP問題的另一個定義問題的另一個定義,這種可以在多項式時間內(nèi)驗這種可以在多項式時間內(nèi)驗證一個解是否正確的問題稱為證一個解是否正確的問題稱為NP問題，亦稱為驗證問題類。問題，亦稱為驗證問題類。簡單的說，存在多項式時間的算法的一類問題，稱之為簡單的說，存在多項式時間的算法的一類問題，稱之為P類問題；而像類問題；而像梵塔問題，推銷員旅行問題等問題，至今沒有找到多項式時間算法解的一類梵塔問題，推銷員旅行問題等問題，至今沒有找到多項式時間算法解的一類問題，稱之為

8、問題，稱之為NP問題。同時，問題。同時，P類問題是類問題是NP問題的一個子集。問題的一個子集。NP完全（ NP Complete,NPC ）問題NPC問題（一） 人們普遍認(rèn)為，人們普遍認(rèn)為，P=NP不成立。那么多數(shù)人相信，存在至少一個不可能有不成立。那么多數(shù)人相信，存在至少一個不可能有多項式級復(fù)雜度的算法的多項式級復(fù)雜度的算法的NP問題問題這就是這就是NPC問題問題。 NPC問題是指這樣一類問題是指這樣一類NP問題問題,所有的所有的NP問題都可以用多項式時間劃歸到問題都可以用多項式時間劃歸到他們中的一個他們中的一個.所以顯然所以顯然NP完全的問題具有如下性質(zhì)完全的問題具有如下性質(zhì):它可以在多項

9、式時它可以在多項式時間內(nèi)求解，當(dāng)且僅當(dāng)所有的其他的間內(nèi)求解，當(dāng)且僅當(dāng)所有的其他的NP完全問題也可以在多項式時間內(nèi)完全問題也可以在多項式時間內(nèi)求解。這樣一來求解。這樣一來,只要我們找到一個只要我們找到一個NPC問題的多項式解問題的多項式解,所有的所有的NP問題都問題都可以多項式時間內(nèi)劃歸成這個可以多項式時間內(nèi)劃歸成這個NPC問題問題,再用多項式時間解決再用多項式時間解決,這樣這樣NP就等就等于于P了了. Reducibility(“約化約化”或或“歸約歸約”)：一個問題一個問題A可以約化為問題可以約化為問題B的含義即的含義即是，可以用解決問題是，可以用解決問題B的解法來解決問題的解法來解決問題A

10、，或者說，問題，或者說，問題A可以可以“變成變成”問題問題B。 如：一元一次方程可以如：一元一次方程可以“歸約歸約”為一元二次方程。為一元二次方程。 問題問題A可可“約化約化”為問題為問題B直觀意義：直觀意義：B的時間復(fù)雜度高于或者等于的時間復(fù)雜度高于或者等于A的時的時間復(fù)雜度。也就是說，問題間復(fù)雜度。也就是說，問題A不比問題不比問題B難。難。 很顯然，約化具有一項重要的性質(zhì)：約化具有傳遞性。如果問題很顯然，約化具有一項重要的性質(zhì)：約化具有傳遞性。如果問題A可約可約化為問題化為問題B，問題，問題B可約化為問題可約化為問題C，則問題，則問題A一定可約化為問題一定可約化為問題C。 現(xiàn)在再來說一下約

11、化的標(biāo)準(zhǔn)概念就不難理解了：如果能現(xiàn)在再來說一下約化的標(biāo)準(zhǔn)概念就不難理解了：如果能找到這樣一個變化法則，對任意一個程序找到這樣一個變化法則，對任意一個程序A的輸入，都能的輸入，都能按這個法則變換成程序按這個法則變換成程序B的輸入，使兩程序的輸出相同，的輸入，使兩程序的輸出相同，那么我們說，問題那么我們說，問題A可約化可約化為問題為問題B。 注：我們所說的注：我們所說的“可約化可約化”是指的可是指的可“多項式地多項式地”約化約化(Polynomial-time Reducible)，即變換輸入的方法是能在，即變換輸入的方法是能在多項式的時間里完成的。約化的過程只有用多項式的時多項式的時間里完成的。

12、約化的過程只有用多項式的時間完成才有意義。間完成才有意義。NPC問題（二）NPC問題（三）NPC問題問題 p問題問題 P問題NP問題問題 p問題問題 約化約化 約化約化總結(jié)：總結(jié)： 定義：定義：同時滿足下面兩個條件的問題就是同時滿足下面兩個條件的問題就是NPC問題。問題。首先，它得是一個首先，它得是一個NP問題；然后，所有的問題；然后，所有的NP問題都問題都可以約化到它。可以約化到它。 證明：證明：先證明它至少是一個先證明它至少是一個NP問題，再證明其中一問題，再證明其中一個已知的個已知的NPC問題能約化到它問題能約化到它 NPC問題（四） NP-Hard問題：其滿足問題：其滿足NPC問題定義

13、的第二條但不一定要問題定義的第二條但不一定要滿足第一條（就是說，滿足第一條（就是說，NP-Hard問題要比問題要比 NPC問題的范圍問題的范圍廣，但不一定是廣，但不一定是NP問題）。問題）。 NP-Hard問題同樣難以找到多項式的算法，但它不列入我問題同樣難以找到多項式的算法，但它不列入我們的研究范圍，因為它不一定是們的研究范圍，因為它不一定是NP問題。即使問題。即使NPC問題問題發(fā)現(xiàn)了多項式級的算法，發(fā)現(xiàn)了多項式級的算法，NP-Hard問題有可能仍然無法得問題有可能仍然無法得到多項式級的算法。事實上，由于到多項式級的算法。事實上，由于NP-Hard放寬了限定條放寬了限定條件，它將有可能比所有

14、的件，它將有可能比所有的NPC問題的時間復(fù)雜度更高從而問題的時間復(fù)雜度更高從而更難以解決。更難以解決。NP-Hard問題？NPC問題（補充）NPC問題存在嗎問題存在嗎? 邏輯電路問題邏輯電路問題: 給定一個邏輯電路，問是否存在一種輸入給定一個邏輯電路，問是否存在一種輸入使輸出為使輸出為True。 這是第一個這是第一個NPC問題。其它的問題。其它的NPC問題都是由這個問題約問題都是由這個問題約化而來的。因此，邏輯電路問題是化而來的。因此，邏輯電路問題是NPC類問題的類問題的“鼻祖鼻祖”。 我們知道，一個邏輯電路由若干個輸入，一個輸出，若干我們知道，一個邏輯電路由若干個輸入，一個輸出，若干“邏輯門邏輯門”和密密麻麻的線組成，如下圖：和密密麻麻的線組成，如下圖： NPC問題（補充） 有輸出無論如何都不可能為有輸出無論如何都不可能為True的邏輯電路的邏輯電路嗎？嗎？ NPC問題（補充） 邏輯電路問題屬于NPC問題它顯然屬于NP問題，并且