什么是p問(wèn)題、np問(wèn)題和npc問(wèn)題(編輯修改稿)
2025-02-09 23:28 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 度加出來(lái)。那么，只要我RP好，猜得準(zhǔn)，我一定能在多項(xiàng)式的時(shí)間里解決這個(gè)問(wèn)題。我猜到的方案總是最優(yōu)的，不滿足題意的方案也不會(huì)來(lái)騙我去選它。這就是NP問(wèn)題。當(dāng)然有不是NP問(wèn)題的問(wèn)題，即你猜到了解但是沒用，因?yàn)槟悴荒茉诙囗?xiàng)式的時(shí)間里去驗(yàn)證它。下面我要舉的例子是一個(gè)經(jīng)典的例子，它指出了一個(gè)目前還沒有辦法在多項(xiàng)式的時(shí)間里驗(yàn)證一個(gè)解的問(wèn)題。很顯然，前面所說(shuō)的Hamilton回路是NP問(wèn)題，因?yàn)轵?yàn)證一條路是否恰好經(jīng)過(guò)了每一個(gè)頂點(diǎn)非常容易。但我要把問(wèn)題換成這樣：試問(wèn)一個(gè)圖中是否不存在Hamilton回路。這樣問(wèn)題就沒法在多項(xiàng)式的時(shí)間里進(jìn)行驗(yàn)證了，因?yàn)槌悄阍囘^(guò)所有的路，否則你不敢斷定它沒有Hamilton回路。之所以要定義NP問(wèn)題，是因?yàn)橥ǔＶ挥蠳P問(wèn)題才可能找到多項(xiàng)式的算法。我們不會(huì)指望一個(gè)連多項(xiàng)式地驗(yàn)證一個(gè)解都不行的問(wèn)題存在一個(gè)解決它的多項(xiàng)式級(jí)的算法。相信讀者很快明白，信息學(xué)中的號(hào)稱最困難的問(wèn)題NP問(wèn)題，實(shí)際上是在探討NP問(wèn)題與P類問(wèn)題的關(guān)系。很顯然，所有的P類問(wèn)題都是NP問(wèn)題。也就是說(shuō)，能多項(xiàng)式地解決一個(gè)問(wèn)題，必然能多項(xiàng)式地驗(yàn)證一個(gè)問(wèn)題的解既然正解都出來(lái)了，驗(yàn)證任意給定的解也只需要比較一下就可以了。關(guān)鍵是，人們想知道，是否所有的NP問(wèn)題都是P類問(wèn)題。我們可以再用集合的觀點(diǎn)來(lái)說(shuō)明。如果把所有P類問(wèn)題歸為一個(gè)集合P中，把所有NP問(wèn)題劃進(jìn)另一個(gè)集合NP中，那么，顯然有P屬于NP。現(xiàn)在，所有對(duì)NP問(wèn)題的研究都集中在一個(gè)問(wèn)題上，即究竟是否有P=NP?通常所謂的NP問(wèn)題，其實(shí)就一句話：證明或推翻P=NP。NP問(wèn)題一直都是信息學(xué)的巔峰。巔峰，意即很引人注目但難以解決。在信息學(xué)研究中，這是一個(gè)耗費(fèi)了很多時(shí)間和精力也沒有解決的終極問(wèn)題，好比物理學(xué)中的大統(tǒng)一和數(shù)學(xué)中的歌德巴赫猜想等。目前為止這個(gè)問(wèn)題還啃不動(dòng)。但是，一個(gè)總的趨勢(shì)、一個(gè)大方向是有的。人們普遍認(rèn)為，P=NP不成立，也就是說(shuō)，多數(shù)人相信，存在至少一個(gè)不可能有多項(xiàng)式級(jí)復(fù)雜度的算法的NP問(wèn)題。人們?nèi)绱藞?jiān)信P≠NP是有原因的，就是在研究NP問(wèn)題的過(guò)程中找出了一類非常特殊的NP問(wèn)題叫做NP完全問(wèn)題，也即所謂的NPC問(wèn)題。C是英文單詞完全的第一個(gè)字母。正是NPC問(wèn)題的存在，使人們相信P≠NP。下文將花大量篇幅介紹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)化為在T
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1