正文內容

什么是p問題、np問題和npc問題-wenkub

2022-09-02 18:58:53 本頁面

　

【正文】 Problem就是一個著名的不可解問題，在我的Blog上有過專門的介紹和證明。容易看出，前面的幾類復雜度被分為兩種級別，其中后者的復雜度無論如何都遠遠大于前者：一種是 O(1),O(log(n)),O(n^a)等，我們把它叫做多項式級的復雜度，因為它的規模n出現在底數的位置；另一種是O(a^n)和O(n!)型復雜度，它是非多項式級的，其復雜度計算機往往不能承受。不會存在O(2*n^2)的復雜度，因為前面的那個“2”是系數，根本不會影響到整個程序的時間增長。時間復雜度并不是表示一個程序解決問題需要花多少時間，而是當問題規模擴大后，程序需要的時間長度增長得有多快。好，行了，基本上這個誤解已經被澄清了。你會經常看到網上出現“這怎么做，這不是NP問題嗎”、“這個只有搜了，這已經被證明是NP問題了”之類的話。你要知道，大多數人此時所說的NP問題其實都是指的NPC問題。下面的內容都是在講什么是P問題，什么是NP問題，什么是NPC 問題，你如果不是很感興趣就可以不看了。也就是說，對于高速處理數據的計算機來說，處理某一個特定數據的效率不能衡量一個程序的好壞，而應該看當這個數據的規模變大到數百倍后，程序運行時間是否還是一樣，或者也跟著慢了數百倍，或者變慢了數萬倍。同樣地，O (n^3+n^2)的復雜度也就是O(n^3)的復雜度。當我們在解決一個問題時，我們選擇的算法通常都需要是多項式級的復雜度，非多項式級的復雜度需要的時間太多，往往會超時，除非是數據規模非常小。再比如，輸出從1到n這n個數的全排列。問題是這樣的：給你一個圖，問你能否找到一條經過每個頂點一次且恰好一次（不遺漏也不重復）最后又走回來的路（滿足這個條件的路徑叫做Hamilton回路）。P是英文單詞多項式的第一個字母。接下來引入NP問題的概念。NP問題的另一個定義是，可以在多項式的時間里猜出一個解的問題。然后我就胡亂畫了幾條線，說就這條吧。在這個題中，找一個解很困難，但驗證一個解很容易。這就是NP問題。但我要把問題換成這樣：試問一個圖中是否不存在Hamilton回路。相信讀者很快明白，信息學中的號稱最困難的問題——“NP問題”，實際上是在探討NP問題與P類問題的關系。我們可以再用集合的觀點來說明。巔峰，意即很引人注目但難以解決。人們普遍認為，P=NP不成立，也就是說，多數人相信，存在至少一個不可能有多項式級復雜度的算法的NP問題。下文將花大量篇幅介紹NPC問題，你從中可以體會到NPC問題使P=NP變得多么不可思議。比如說，現在有兩個問題：求解一個一元一次方程和求解一個一元二次方程。按照這個規則把前一個問題轉換成后一個問題，兩個問題就等價了。也就是說，問題A不比問題B難。很顯然，約化具有一項重要的性質：約化具有傳遞性。當然，我們所說的“可約化”是指的可“多項式地”約化(Polynomialtime Reducible)，即變換輸入的方法是能在多項式的時間里完成的。再回想前面講的P和NP問題，聯想起約化的傳遞性，自然地，我們會想問，如果不斷地約化上去，不斷找到能“通吃”若干小NP問題的一個稍復雜的大NP問題

點擊復制文檔內容

公司管理相關推薦

鄂ICP備17016276號-1

<meter id="zdgym"><samp id="zdgym"></samp></meter>

什么是p問題、np問題和npc問題-wenkub

現狀和問題-資料下載頁

和倍問題-資料下載頁

行程問題——流水問題、過橋問題-資料下載頁

p2p網貸風控之真問題-資料下載頁

酒店常見問題及處理p12-資料下載頁

中醫解釋眼睛干澀是肝問題-資料下載頁

靜力學問題和動力學問題-資料下載頁

8作風問題本質上是一個政治問題-資料下載頁

假設檢驗問題的p值法-資料下載頁

p2p網絡借貸中存在的問題及其法律規制-資料下載頁

什么是轉正定級？人才市場人事代理問題剖析推薦-資料下載頁

差倍問題專項問題-資料下載頁

qbq：問題背后的問題-資料下載頁

工程問題公式注水問題-資料下載頁

行程問題6變速問題-資料下載頁

什么是p問題、np問題和npc問題-文庫吧

什么是p問題、np問題和npc問題-wenkub

什么是p問題、np問題和npc問題(已修改)

什么是p問題、np問題和npc問題(編輯修改稿)

什么是p問題、np問題和npc問題-wenkub.com