什么是p問(wèn)題、np問(wèn)題和npc問(wèn)題(編輯修改稿)
2025-09-01 18:58 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 篇幅介紹NPC問(wèn)題，你從中可以體會(huì)到NPC問(wèn) 題使P=NP變得多么不可思議。為了說(shuō)明NPC問(wèn)題，我們先引入一個(gè)概念——約化(Reducibility，有的資料上叫“歸約”)。簡(jiǎn) 單地說(shuō)，一個(gè)問(wèn)題A可以約化為問(wèn)題B的含義即是，可以用問(wèn)題B的解法解決問(wèn)題A，或者說(shuō)，問(wèn)題A可以“變成”問(wèn)題B?！端惴▽?dǎo)論》上舉了這么一個(gè)例子。比 如說(shuō)，現(xiàn)在有兩個(gè)問(wèn)題：求解一個(gè)一元一次方程和求解一個(gè)一元二次方程。那么我們說(shuō)，前者可以約化為后者，意即知道如何解一個(gè)一元二次方程那么一定能解出一 元一次方程。我們可以寫出兩個(gè)程序分別對(duì)應(yīng)兩個(gè)問(wèn)題，那么我們能找到一個(gè)“規(guī)則”，按照這個(gè)規(guī)則把解一元一次方程程序的輸入數(shù)據(jù)變一下，用在解一元二次方 程的程序上，兩個(gè)程序總能得到一樣的結(jié)果。這個(gè)規(guī)則即是：兩個(gè)方程的對(duì)應(yīng)項(xiàng)系數(shù)不變，一元二次方程的二次項(xiàng)系數(shù)為0。按照這個(gè)規(guī)則把前一個(gè)問(wèn)題轉(zhuǎn)換成后一 個(gè)問(wèn)題，兩個(gè)問(wèn)題就等價(jià)了。同樣地，我們可以說(shuō)，Hamilton回路可以約化為TSP問(wèn)題(Travelling Salesman Problem，旅行商問(wèn)題)：在Hamilton回路問(wèn)題中，兩點(diǎn)相連即這兩點(diǎn)距離為0，兩點(diǎn)不直接相連則令其距離為1，于是問(wèn)題轉(zhuǎn)化為在TSP問(wèn)題 中，是否存在一條長(zhǎng)為0的路徑。Hamilton回路存在當(dāng)且僅當(dāng)TSP問(wèn)題中存在長(zhǎng)為0的回路?！皢?wèn)題A可約化為問(wèn)題B”有一個(gè)重要的 直觀意義：B的時(shí)間復(fù)雜度高于或者等于A的時(shí)間復(fù)雜度。也就是說(shuō)，問(wèn)題A不比問(wèn)題B難。這很容易理解。既然問(wèn)題A能用問(wèn)題B來(lái)解決，倘若B的時(shí)間復(fù)雜度比 A的時(shí)間復(fù)雜度還低了，那A的算法就可以改進(jìn)為B的算法，兩者的時(shí)間復(fù)雜度還是相同。正如解一元二次方程比解一元一次方程難，因?yàn)榻鉀Q前者的方法可以用來(lái) 解決后者。很顯然，約化具有一項(xiàng)重要的性質(zhì)：約化具有傳遞性。如果問(wèn)題A可約化為問(wèn)題B，問(wèn)題B可約化為問(wèn)題C，則問(wèn)題A一定可約化為問(wèn)題C。這個(gè)道理非常簡(jiǎn)單，就不必闡述了。現(xiàn)在再來(lái)說(shuō)一下約化的標(biāo)準(zhǔn)概念就不難理解了：如果能找到這樣一個(gè)變化法則，對(duì)任意一個(gè)程序A的輸入，都能按這個(gè)法則變換成程序B的輸入，使兩程序的輸出相同，那么我們說(shuō)，問(wèn)題A可約化為問(wèn)題B。當(dāng)然，我們所說(shuō)的“可約化”是指的可“多項(xiàng)式地”約化(Polynomialtime Reducible)，即變換輸入的方法是能在多項(xiàng)式的時(shí)間里完成的。約化的過(guò)程只有用多項(xiàng)式的時(shí)間完成才有意義。好 了，從約化的定義中我們看到，一個(gè)問(wèn)題約化為另一個(gè)問(wèn)題，時(shí)間復(fù)雜度增加了，問(wèn)題的應(yīng)用范圍也增大了。通過(guò)對(duì)某些問(wèn)題的不斷約化，我們能夠不斷尋找復(fù)雜度 更高，但應(yīng)用范圍更廣的算法來(lái)代替復(fù)雜度雖然低，但只能用于很小的一類問(wèn)題的算法。再回想前面講的P和NP問(wèn)題，聯(lián)想起約化的傳遞性，自然地，我們會(huì)想 問(wèn)，如果不斷地約化上去，不斷找到能“通吃”若干小NP問(wèn)題的一個(gè)稍復(fù)雜的大NP問(wèn)題，那么最后是否有可能找到一個(gè)時(shí)間復(fù)雜度最高，并且能“通吃”所有的 NP問(wèn)題的這樣一個(gè)超級(jí)NP問(wèn)題？答案居然是肯定的。也就是說(shuō)，存在這樣一個(gè)NP問(wèn)題，所有的NP問(wèn)題都可以約化成它。換句話說(shuō)，只要解決了這個(gè)問(wèn)題，那 么所有的NP問(wèn)題都解決了。這種問(wèn)題的存在難以置信，并且更加不可思議的是，這種問(wèn)題不只一個(gè)，它有很多個(gè)，它是一類問(wèn)題。這一類問(wèn)題就是傳說(shuō)中的NPC 問(wèn)題，也就是NP完全問(wèn)題。NPC問(wèn)題的出現(xiàn)使整個(gè)NP問(wèn)題的研究得到了飛躍式的發(fā)展。我們有理由相信，NPC問(wèn)題是最復(fù)雜的問(wèn)題。再次回到全文開(kāi)頭， 我們可以看到，人們想表達(dá)一個(gè)問(wèn)題不存在多項(xiàng)式的高效算法時(shí)應(yīng)該說(shuō)它“屬于NPC問(wèn)題”。此時(shí)，我的目的終于達(dá)到了，我已經(jīng)把NP問(wèn)題和NPC問(wèn)題區(qū)別開(kāi) 了。到此為止，本文已經(jīng)寫了近5000字了，我佩服你還能看到這里來(lái)，同時(shí)也佩服一下自己能寫到這里來(lái)。
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1