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ù)雜度P問題是可以在多項式時間內(nèi)被確定機(通常意義的計算機)解決的問題.如果一個問題可以找到一個能在多項式的時間里解決它的算法，那么這個問題就屬于P問題。我們常見到的一些信息奧賽的題目都是P問題。P問題VSNP問題？P(Polynomial,多項式)問題NP(Non-DeterministicPolynomial,非確定多項式)問題首先：NP問題不是非P類問題！NP問題,是指可以在多項式時間內(nèi)被非確定機(他可以猜,他總是能猜到最能滿足你需要的那種選擇,如果你讓他解決n皇后問題,他只要猜n次就能完成----每次都是那么幸運)解決的問題.這里有一個著名的問題----千禧難題之首,是說P問題是否等于NP問題,也即是否所有在非確定機上多項式可解的問題都能在確定機上用多項式時間求解.NP問題是指可以在多項式的時間里驗證一個解的問題，即可以在多項式的時間里猜出一個解的問題。像Hamilton回路問題。在這個題中，找一個解很困難，但驗證一個解很容易。當(dāng)然有不是NP問題的問題，即咱猜到了解但是沒用，因為咱不能在多項式的時間里去驗證它。如下面這個：

我們已經(jīng)知道Hamilton回路是NP問題，因為驗證一條路是否恰好經(jīng)過了每一個頂點非常容易。但我們把問題換成這樣：試問一個圖中是否不存在Hamilton回路。這樣問題就沒法在多項式的時間里進(jìn)行驗證了，因為除非你試過所有的路，否則你不敢斷定它“沒有Hamilton回路”。

已經(jīng)知道所有的P類問題都是NP問題。那反之呢？其實就一句話：證明或推翻P=NP——這就是所謂的“NP問題”！P問題與NP問題的對比

換一種說法,如果一個問題的復(fù)雜度是該問題的一個實例規(guī)模n的多項式函數(shù)，則這種可以在多項式時間內(nèi)解決的問題屬于P類問題.通俗地稱所有復(fù)雜度為多項式時間的問題為易解的問題類，否則為難解的問題。有些問題很難找到多項式時間的算法（或許根本不存在），例如“找出無向圖中哈密頓回路”問題。但如果給了該問題的一個答案，可以在多項式時間內(nèi)判斷這個答案是否正確。例如說對于哈密頓回路問題，給一個任意的回路，很容易判斷它是否是哈密頓回路（只要看是不是所有的頂點都在回路中就可以了）。這里給出NP問題的另一個定義,這種可以在多項式時間內(nèi)驗證一個解是否正確的問題稱為NP問題，亦稱為驗證問題類。簡單的說，存在多項式時間的算法的一類問題，稱之為P類問題；而像梵塔問題，推銷員旅行問題等問題，至今沒有找到多項式時間算法解的一類問題，稱之為NP問題。同時，P類問題是NP問題的一個子集。NP完全（NPComplete,NPC）問題

NPC問題（一）人們普遍認(rèn)為，P=NP不成立。那么多數(shù)人相信，存在至少一個不可能有多項式級復(fù)雜度的算法的NP問題——這就是NPC問題。NPC問題是指這樣一類NP問題,所有的NP問題都可以用多項式時間劃歸到他們中的一個.所以顯然NP完全的問題具有如下性質(zhì):它可以在多項式時間內(nèi)求解，當(dāng)且僅當(dāng)所有的其他的NP－完全問題也可以在多項式時間內(nèi)求解。這樣一來,只要我們找到一個NPC問題的多項式解,所有的NP問題都可以多項式時間內(nèi)劃歸成這個NPC問題,再用多項式時間解決,這樣NP就等于P了.Reducibility(“約化”或“歸約”)：一個問題A可以約化為問題B的含義即是，可以用解決問題B的解法來解決問題A，或者說，問題A可以“變成”問題B。如：一元一次方程可以“歸約”為一元二次方程。問題A可“約化”為問題B直觀意義：B的時間復(fù)雜度高于或者等于A的時間復(fù)雜度。也就是說，問題A不比問題B難。很顯然，約化具有一項重要的性質(zhì)：約化具有傳遞性。如果問題A可約化為問題B，問題B可約化為問題C，則問題A一定可約化為問題C。NPC問題（三）NPC問題

p問題

P問題NP問題

p問題約化

約化NP-Hard問題：其滿足NPC問題定義的第二條但不一定要滿足第一條（就是說，NP-Hard問題要比NPC問題的范圍廣，但不一定是NP問題）。NP-Hard問題同樣難以找到多項式的算法，但它不列入我們的研究范圍，因為它不一定是NP問題。即使NPC問題發(fā)現(xiàn)了多項式級的算法，NP-Hard問題有可能仍然無法得到多項式級的算法。事實上，由于NP-Hard放寬了限定條件，它將有可能比所有的NPC問題的時間復(fù)雜度更高從而更難以解決。NP-Hard問題邏輯電路問題:給定一個邏輯電路，問是否存在一種輸入使輸出為True。這是第一個NPC問題。其它的NPC問題都是由這個問題約化而來的。因此，邏輯電路問題是NPC類問題的“鼻祖”。我們知道，一個邏輯電路由若干個輸入，一個輸出，若干“邏輯門”和密密麻麻的線組成，如下圖：

NPC問題（補充）有輸出無論如何都不可能為True的邏輯電路嗎？

NPC問題（補充）邏輯電路問題屬于NPC問題——它顯然屬于NP問題，并且可以證明所有的NP問題都可以約化到它。NP