什么是p問題、np問題和npc問題(完整版)
【正文】 復(fù)雜度也就是O(n^3)的復(fù)雜度。當(dāng)我們在解決一個問題時，我們選擇的算法通常都需要是多項式級的復(fù)雜度，非多項式級的復(fù)雜度需要的 時間太多，往往會超時，除非是數(shù)據(jù)規(guī)模非常小。再比如，輸出從1到n這n個數(shù)的全排列。NP問題的另一個定義是，可以在多項式的時間里猜出一個解的 問題。在這個題中，找一個解很困難，但驗證一個解很容易。但我要把 問題換成這樣：試問一個圖中是否不存在Hamilton回路。相信讀者很快明白，信息學(xué)中的號稱最困難的問題——“NP問題”，實際上是在探討NP問題與P類問題的關(guān) 系。我們可以再用集合的觀點來說明。巔峰，意即很引人注目但難以解決。人們普遍認為，P=NP不成立，也就是說，多數(shù)人相信，存在至少一個不可能有多項式 級復(fù)雜度的算法的NP問題。比 如說，現(xiàn)在有兩個問題：求解一個一元一次方程和求解一個一元二次方程。當(dāng)然，我們所說的“可約化”是指的可“多項式地”約化(Polynomialtime Reducible)，即變換輸入的方法是能在多項式的時間里完成的。再回想前面講的P和NP問題，聯(lián)想起約化的傳遞性，自然地，我們會想 問，如果不斷地約化上去，不斷找到能“通吃”若干小NP問題的一個稍復(fù)雜的大NP問題，那么最后是否有可能找到一個時間復(fù)雜度最高，并且能“通吃”所有的 NP問題的這樣一個超級NP問題？答案居然是肯定的。此時，我的目的終于達到了，我已經(jīng)把NP問題和NPC問題區(qū)別開 了。首先，它得是一個NP問題；然后，所有的NP問題都可以約化到它。因此，給NPC找一個多項式算法太不可思議了。NPHard問題是這樣一種 問題，它滿足NPC問題定義的第二條但不一定要滿足第一條（就是說，NPHard問題要比 NPC問題的范圍廣）。不要以為NPC問題是一紙空談。下文即將介紹邏輯電路問題。邏輯電路問題是指的這樣一個問題：給定一個邏輯電路，問是否存在一種輸入使輸出為True。┌──┐│AND ├─→┐┌─→┤│││┌───┐│AND ├─→輸出└───┘Matrix67原創(chuàng)轉(zhuǎn)載請注明出處。后來，Hamilton 回路成了NPC問題，TSP問題也成了NPC問題。這是有嚴格證明的。└──┘┌→┤│輸入2 ├→─┤└→┤│┌──┐│└───┘┌───┐其它的NPC問題都是由這個問題約化而來的。確實有這么一個非常具體的問題屬于NPC問題。即使NPC問題發(fā)現(xiàn)了多項式級 的算法，NPHard問題有可能仍然無法得到多項式級的算法。我們可以就此直觀地理解，NPC問題 目前沒有多項式的有效算法，只能用指數(shù)級甚至階乘級復(fù)雜度的搜索。先證明它至少是一個NP問題，再證明其中一個已知的NPC問題能約化到它（由約化的傳遞性，則NPC問題定義的第二條也得以滿足；至 于第一個NPC問題是怎么來的，下文將介紹），這樣就可以說它是NPC問題了。換句話說，只要解決了這個問題，那 么所有的NP問題都解決了。我們可以寫出兩個程序分別對應(yīng)兩個問題，那么我們能找到一個“規(guī)則”，按照這個規(guī)則把解一元一次方程程序的輸入數(shù)據(jù)變一下，用在解一元二次方 程的程序上，兩個程
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1