什么是p問(wèn)題、np問(wèn)題和npc問(wèn)題(專業(yè)版)

　　

【正文】 有了第一個(gè)NPC 問(wèn)題后，一大堆NPC問(wèn)題就出現(xiàn)了，因?yàn)樵僮C明一個(gè)新的NPC問(wèn)題只需要將一個(gè)已知的NPC問(wèn)題約化到它就行了。這是個(gè)較簡(jiǎn)單的邏輯電路，當(dāng)輸入輸入輸入3分別為T(mén)rue、True、False或False、True、False時(shí)，輸出為T(mén)rue。│││┌───┐這是第一個(gè)NPC問(wèn)題。NPHard問(wèn)題同樣難以找到多項(xiàng)式的算法，但它不列入我們的研究范圍，因?yàn)樗灰欢ㄊ荖P問(wèn)題。證明一個(gè)問(wèn)題是 NPC問(wèn)題也很簡(jiǎn)單。也就是說(shuō)，存在這樣一個(gè)NP問(wèn)題，所有的NP問(wèn)題都可以約化成它。為了說(shuō)明NPC問(wèn)題，我們先引入一個(gè)概念——約化(Reducibility，有的資料上叫“歸約”)。在信息學(xué)研究中，這是一個(gè)耗費(fèi)了很多時(shí)間和精力也沒(méi)有解決的終極問(wèn)題，好比物理學(xué)中的大統(tǒng)一和數(shù)學(xué)中的歌德巴赫猜想等。驗(yàn)證一個(gè)解只需要O(n)的時(shí)間復(fù)雜度，也就是說(shuō)我可以花O(n)的時(shí)間把我猜的路徑的長(zhǎng)度加 出來(lái)。不管你用什么方法，你的復(fù)雜度都是階乘級(jí)，因?yàn)?你總得用階乘級(jí)的時(shí)間打印出結(jié)果來(lái)。因此，我們會(huì)說(shuō)，一個(gè)O(*n^3)的程序的效率比O(100*n^2)的效率低，盡管 在n很小的時(shí)候，前者優(yōu)于后者，但后者時(shí)間隨數(shù)據(jù)規(guī)模增長(zhǎng)得慢，最終O(n^3)的復(fù)雜度將遠(yuǎn)遠(yuǎn)超過(guò)O(n^2)。他們沒(méi)有搞清楚NP問(wèn)題和NPC問(wèn)題的概念。這或許是眾多OIer最大的誤區(qū)之一。還是先用幾句話簡(jiǎn)單 說(shuō)明一下時(shí)間復(fù)雜度。現(xiàn)在某人拿到了一個(gè)求最短路徑的問(wèn)題，問(wèn)從起點(diǎn)到終點(diǎn)是否有一條小于100個(gè)單位長(zhǎng)度 的路線。現(xiàn)在，所有對(duì)NP問(wèn)題的研究都集中在一個(gè)問(wèn)題上，即究竟是否有P=NP？通常所謂的“NP問(wèn) 題”，其實(shí)就一句話：證明或推翻P=NP。C是英文單詞“完全”的第一個(gè)字母。我們可以寫(xiě)出兩個(gè)程序分別對(duì)應(yīng)兩個(gè)問(wèn)題，那么我們能找到一個(gè)“規(guī)則”，按照這個(gè)規(guī)則把解一元一次方程程序的輸入數(shù)據(jù)變一下，用在解一元二次方 程的程序上，兩個(gè)程序總能得到一樣的結(jié)果。我們可以就此直觀地理解，NPC問(wèn)題 目前沒(méi)有多項(xiàng)式的有效算法，只能用指數(shù)級(jí)甚至階乘級(jí)復(fù)雜度的搜索。確實(shí)有這么一個(gè)非常具體的問(wèn)題屬于NPC問(wèn)題。┌───┐│┌→┤└──┘這是有嚴(yán)格證明的。Matrix67原創(chuàng)轉(zhuǎn)載請(qǐng)注明出處。┌───┐││邏輯電路問(wèn)題是指的這樣一個(gè)問(wèn)題：給定一個(gè)邏輯電路，問(wèn)是否存在一種輸入使輸出為T(mén)rue。不要以為NPC問(wèn)題是一紙空談。因此，給NPC找一個(gè)多項(xiàng)式算法太不可思議了。此時(shí)，我的目的終于達(dá)到了，我已經(jīng)把NP問(wèn)題和NPC問(wèn)題區(qū)別開(kāi) 了。當(dāng)然，我們所說(shuō)的“可約化”是指的可“多項(xiàng)式地”約化(Polynomialtime Reducible)，即變換輸入的方法是能在多項(xiàng)式的時(shí)間里完成的。比 如說(shuō)，現(xiàn)在有兩個(gè)問(wèn)題：求解一個(gè)一元一次方程和求解一個(gè)一元二次方程。人們普遍認(rèn)為，P=NP不成立，也就是說(shuō)，多數(shù)人相信，存在至少一個(gè)不可能有多項(xiàng)式 級(jí)復(fù)雜度的算法的NP問(wèn)題。我們可以再用集合的觀點(diǎn)來(lái)說(shuō)明。但我要把 問(wèn)題換成這樣：試問(wèn)一個(gè)圖中是否不存在Hamilton回路。NP問(wèn)題的另一個(gè)定義是，可以在多項(xiàng)式的時(shí)間里猜出一個(gè)解的 問(wèn)題。當(dāng)我們?cè)?