什么是p問(wèn)題、np問(wèn)題和npc問(wèn)題-閱讀頁(yè)
2024-08-24 18:58本頁(yè)面
【正文】 元一次方程難，因?yàn)榻鉀Q前者的方法可以用來(lái) 解決后者。如果問(wèn)題A可約化為問(wèn)題B，問(wèn)題B可約化為問(wèn)題C，則問(wèn)題A一定可約化為問(wèn)題C?，F(xiàn)在再來(lái)說(shuō)一下約化的標(biāo)準(zhǔn)概念就不難理解了：如果能找到這樣一個(gè)變化法則，對(duì)任意一個(gè)程序A的輸入，都能按這個(gè)法則變換成程序B的輸入，使兩程序的輸出相同，那么我們說(shuō)，問(wèn)題A可約化為問(wèn)題B。約化的過(guò)程只有用多項(xiàng)式的時(shí)間完成才有意義。通過(guò)對(duì)某些問(wèn)題的不斷約化，我們能夠不斷尋找復(fù)雜度 更高，但應(yīng)用范圍更廣的算法來(lái)代替復(fù)雜度雖然低，但只能用于很小的一類問(wèn)題的算法。也就是說(shuō)，存在這樣一個(gè)NP問(wèn)題，所有的NP問(wèn)題都可以約化成它。這種問(wèn)題的存在難以置信，并且更加不可思議的是，這種問(wèn)題不只一個(gè)，它有很多個(gè)，它是一類問(wèn)題。NPC問(wèn)題的出現(xiàn)使整個(gè)NP問(wèn)題的研究得到了飛躍式的發(fā)展。再次回到全文開頭， 我們可以看到，人們想表達(dá)一個(gè)問(wèn)題不存在多項(xiàng)式的高效算法時(shí)應(yīng)該說(shuō)它“屬于NPC問(wèn)題”。到此為止，本文已經(jīng)寫了近5000字了，我佩服你還能看到這里來(lái)，同時(shí)也佩服一下自己能寫到這里來(lái)。同時(shí)滿足下面兩個(gè)條件的問(wèn)題就是NPC問(wèn)題。證明一個(gè)問(wèn)題是 NPC問(wèn)題也很簡(jiǎn)單。既然所有的NP問(wèn)題都能約化成NPC問(wèn)題，那么只要任意一 個(gè)NPC問(wèn)題找到了一個(gè)多項(xiàng)式的算法，那么所有的NP問(wèn)題都能用這個(gè)算法解決了，NP也就等于P 了。因此，前文才說(shuō)，“正是NPC問(wèn)題的存在，使人們相信P≠NP”。順便講一下NPHard問(wèn)題。NPHard問(wèn)題同樣難以找到多項(xiàng)式的算法，但它不列入我們的研究范圍，因?yàn)樗灰欢ㄊ荖P問(wèn)題。事實(shí)上，由于NPHard放寬了限定條件，它將有可能比所有的NPC問(wèn)題的時(shí)間復(fù)雜度更 高從而更難以解決。NPC問(wèn)題是存在的。下文即將介紹它。這是第一個(gè)NPC問(wèn)題。因此，邏輯電路問(wèn)題是NPC類問(wèn)題的“鼻祖”。什么叫做邏輯電路呢？一個(gè)邏輯電路由若干個(gè)輸入，一個(gè)輸出，若干“邏輯門”和密密麻麻的線組成。┌───┐│ 輸入1├─→┐┌──┐└───┘└─→┤││ or ├→─┐┌───┐┌─→┤││┌──┐│ 輸入2├─→┤└──┘└─→┤│└───┘│┌─→┤AND ├──→輸出└────────┘┌→┤│┌───┐┌──┐│└──┘│ 輸入3├─→┤ NOT├─→────┘└───┘└──┘這是個(gè)較簡(jiǎn)單的邏輯電路，當(dāng)輸入輸入輸入3分別為True、True、False或False、True、False時(shí)，輸出為True。下面就是一個(gè)簡(jiǎn)單的例子。我們就說(shuō)，這個(gè)邏輯電路不存在使輸出為True的一組輸入。邏 輯電路問(wèn)題屬于NPC問(wèn)題。它顯然屬于NP問(wèn)題，并且可以直接證明所有的NP問(wèn)題都可以約化到它（不要以為NP問(wèn)題有無(wú)窮多個(gè)將給證明 造成不可逾越的困難）。有了第一個(gè)NPC 問(wèn)題后，一大堆NPC問(wèn)題就出現(xiàn)了，因?yàn)樵僮C明一個(gè)新的NPC問(wèn)題只需要將一個(gè)已知的NPC問(wèn)題約化到它就行了?，F(xiàn)在被證明是NPC問(wèn)題的有很多，任何一個(gè)找到了多項(xiàng)式算法的話所有的NP問(wèn)題都可以完美解決了。P=NP問(wèn)題還有許多有趣的東西，有待大家自己進(jìn)一步的挖掘?，F(xiàn)在我們需要做的，至少是不要把概念弄
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1