什么是p問(wèn)題、np問(wèn)題和npc問(wèn)題-文庫(kù)吧資料
2024-08-17 13:53本頁(yè)面
【正文】 。這個(gè)道理非常簡(jiǎn)單，就不必闡述了。很顯然，約化具有一項(xiàng)重要的性質(zhì)：約化具有傳遞性。既然問(wèn)題A能用問(wèn)題B來(lái)解決，倘若B的時(shí)間復(fù)雜度比 A的時(shí)間復(fù)雜度還低了，那A的算法就可以改進(jìn)為B的算法，兩者的時(shí)間復(fù)雜度還是相同。也就是說(shuō)，問(wèn)題A不比問(wèn)題B難。Hamilton回路存在當(dāng)且僅當(dāng)TSP問(wèn)題中存在長(zhǎng)為0的回路。按照這個(gè)規(guī)則把前一個(gè)問(wèn)題轉(zhuǎn)換成后一 個(gè)問(wèn)題，兩個(gè)問(wèn)題就等價(jià)了。我們可以寫(xiě)出兩個(gè)程序分別對(duì)應(yīng)兩個(gè)問(wèn)題，那么我們能找到一個(gè)“規(guī)則”，按照這個(gè)規(guī)則把解一元一次方程程序的輸入數(shù)據(jù)變一下，用在解一元二次方 程的程序上，兩個(gè)程序總能得到一樣的結(jié)果。比 如說(shuō)，現(xiàn)在有兩個(gè)問(wèn)題：求解一個(gè)一元一次方程和求解一個(gè)一元二次方程。簡(jiǎn) 單地說(shuō)，一個(gè)問(wèn)題A可以約化為問(wèn)題B的含義即是，可以用問(wèn)題B的解法解決問(wèn)題A，或者說(shuō)，問(wèn)題A可以“變成”問(wèn)題B。下文將花大量篇幅介紹NPC問(wèn)題，你從中可以體會(huì)到NPC問(wèn) 題使P=NP變得多么不可思議。C是英文單詞“完全”的第一個(gè)字母。人們普遍認(rèn)為，P=NP不成立，也就是說(shuō)，多數(shù)人相信，存在至少一個(gè)不可能有多項(xiàng)式 級(jí)復(fù)雜度的算法的NP問(wèn)題。目 前為止這個(gè)問(wèn)題還“啃不動(dòng)”。巔峰，意即很引人注目但難以解決?，F(xiàn)在，所有對(duì)NP問(wèn)題的研究都集中在一個(gè)問(wèn)題上，即究竟是否有P=NP？通常所謂的“NP問(wèn) 題”，其實(shí)就一句話：證明或推翻P=NP。我們可以再用集合的觀點(diǎn)來(lái)說(shuō)明。也就是說(shuō)，能多項(xiàng)式地解決一個(gè)問(wèn)題，必然能多項(xiàng)式地驗(yàn)證一個(gè)問(wèn)題的解——既然正解都出 來(lái)了，驗(yàn)證任意給定的解也只需要比較一下就可以了。相信讀者很快明白，信息學(xué)中的號(hào)稱最困難的問(wèn)題——“NP問(wèn)題”，實(shí)際上是在探討NP問(wèn)題與P類問(wèn)題的關(guān) 系。之所以要定義NP問(wèn)題，是因?yàn)橥ǔＶ挥蠳P問(wèn)題才可能找到多項(xiàng)式的算法。但我要把 問(wèn)題換成這樣：試問(wèn)一個(gè)圖中是否不存在Hamilton回路。下面我要舉的例子是一個(gè)經(jīng)典的例子，它指出了一個(gè)目前還沒(méi)有 辦法在多項(xiàng)式的時(shí)間里驗(yàn)證一個(gè)解的問(wèn)題。這就是NP問(wèn) 題。那么，只要我RP好，猜得準(zhǔn)，我一定能在多項(xiàng)式的時(shí)間里解決這個(gè)問(wèn)題。在這個(gè)題中，找一個(gè)解很困難，但驗(yàn)證一個(gè)解很容易。于是答案出來(lái)了，存在比100小的路徑。然后我就胡亂 畫(huà)了幾條線，說(shuō)就這條吧?，F(xiàn)在某人拿到了一個(gè)求最短路徑的問(wèn)題，問(wèn)從起點(diǎn)到終點(diǎn)是否有一條小于100個(gè)單位長(zhǎng)度 的路線。NP問(wèn)題的另一個(gè)定義是，可以在多項(xiàng)式的時(shí)間里猜出一個(gè)解的 問(wèn)題。在這里強(qiáng)調(diào)（回到我竭力想澄 清的誤區(qū)上），NP問(wèn)題不是非P類問(wèn)題。接下來(lái)引入NP問(wèn)題的概念。我們常見(jiàn)到的一些信息奧賽的題目都是P問(wèn)題。P是英文單詞多項(xiàng)式的第一個(gè)字母。事實(shí)上，這個(gè)問(wèn)題就是我們后面要說(shuō)的NPC問(wèn)題。問(wèn)題是這樣的：給你一個(gè)圖，問(wèn)你能否找到一條經(jīng)過(guò)每個(gè)頂點(diǎn)一次且恰好一次（不遺漏也不重復(fù)）最后又走回來(lái)的路（滿足這個(gè)條件的 路徑叫做Hamilton回路）。有人說(shuō)，這樣的“問(wèn)題”不是一個(gè)“正規(guī)”的問(wèn)題，正規(guī)的問(wèn)題是讓程序解決一個(gè)問(wèn)題，輸出一個(gè)“YES”或“NO”（這 被稱為判定性問(wèn)題），或者一個(gè)什么什么的最優(yōu)值（這被稱為最優(yōu)化問(wèn)題）。再比如，輸出從1到n這n個(gè)數(shù)的全排列。有些問(wèn)題甚至根本不可能找到一個(gè)正確的算法
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1