什么是p問題、np問題和npc問題-預(yù)覽頁
【正文】 印出結(jié)果來。這個(gè)問題現(xiàn)在還沒有找到多項(xiàng)式級的算法。哪些問題是 P類問題呢？通常NOI和NOIP不會出不屬于P類問題的題目。這個(gè)就有點(diǎn)難理解了，或者說容易理解錯誤。比方說，我RP很好，在程序中需要枚舉時(shí)，我可以一猜一個(gè)準(zhǔn)。那人按我指的這條把權(quán)值加起來一看，嘿，神了，路徑長度98，比100小。驗(yàn)證一個(gè)解只需要O(n)的時(shí)間復(fù)雜度，也就是說我可以花O(n)的時(shí)間把我猜的路徑的長度加 出來。當(dāng)然有不是NP問題的問題，即你猜到了解但是沒用，因?yàn)槟悴荒茉诙囗?xiàng)式的時(shí)間里去驗(yàn)證它。這樣問題就沒法在多項(xiàng)式的時(shí)間里進(jìn)行驗(yàn)證了，因?yàn)槌悄阍囘^所有的路，否則你不敢斷定它“沒 有Hamilton回路”。很顯然，所有的P類問題都是NP問題。如果把所有P類 問題歸為一個(gè)集合P中，把所有 NP問題劃進(jìn)另一個(gè)集合NP中，那么，顯然有P屬于NP。在信息學(xué)研究中，這是一個(gè)耗費(fèi)了很多時(shí)間和精力也沒有解決的終極問題，好比物理學(xué)中的大統(tǒng)一和數(shù)學(xué)中的歌德巴赫猜想等。人們?nèi)绱藞?jiān)信P≠NP是有原因的，就是在研究NP問題的過程中找出了一類非常特殊的NP問題叫做NP完全問題，也即所謂的 NPC問題。為了說明NPC問題，我們先引入一個(gè)概念——約化(Reducibility，有的資料上叫“歸約”)。那么我們說，前者可以約化為后者，意即知道如何解一個(gè)一元二次方程那么一定能解出一 元一次方程。同樣地，我們可以說，Hamilton回路可以約化為TSP問題(Travelling Salesman Problem，旅行商問題)：在Hamilton回路問題中，兩點(diǎn)相連即這兩點(diǎn)距離為0，兩點(diǎn)不直接相連則令其距離為1，于是問題轉(zhuǎn)化為在TSP問題 中，是否存在一條長為0的路徑。這很容易理解。如果問題A可約化為問題B，問題B可約化為問題C，則問題A一定可約化為問題C。約化的過程只有用多項(xiàng)式的時(shí)間完成才有意義。也就是說，存在這樣一個(gè)NP問題，所有的NP問題都可以約化成它。NPC問題的出現(xiàn)使整個(gè)NP問題的研究得到了飛躍式的發(fā)展。到此為止，本文已經(jīng)寫了近5000字了，我佩服你還能看到這里來，同時(shí)也佩服一下自己能寫到這里來。證明一個(gè)問題是 NPC問題也很簡單。因此，前文才說，“正是NPC問題的存在，使人們相信P≠NP”。NPHard問題同樣難以找到多項(xiàng)式的算法，但它不列入我們的研究范圍，因?yàn)樗灰欢ㄊ荖P問題。NPC問題是存在的。這是第一個(gè)NPC問題。什么叫做邏輯電路呢？一個(gè)邏輯電路由若干個(gè)輸入，一個(gè)輸出，若干“邏輯門”和密密麻麻的線組成。┌───┐└───┘└─→┤│┌───┐┌─→┤││┌──┐└───┘│┌─→┤AND ├──→輸出└────────┘┌→┤│└──┘└───┘└──┘這是個(gè)較簡單的邏輯電路，當(dāng)輸入輸入輸入3分別為True、True、False或False、True、False時(shí)，輸出為True。邏 輯電路問題屬于NPC問題。有了第一個(gè)NPC 問題后，一大堆NPC問題就出現(xiàn)了，因?yàn)樵僮C明一個(gè)新的NPC問題只需要將一個(gè)已知的NPC問題約化到它就行了。P=NP問題還有許多有趣的東西，有待大家自己進(jìn)一步
公司管理相關(guān)推薦
鄂ICP備17016276號-1