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