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