什么是p問(wèn)題、np問(wèn)題和npc問(wèn)題(文件)
【正文】 ，那么最后是否有可能找到一個(gè)時(shí)間復(fù)雜度最高，并且能“通吃”所有的 NP問(wèn)題的這樣一個(gè)超級(jí)NP問(wèn)題？答案居然是肯定的。這一類問(wèn)題就是傳說(shuō)中的NPC 問(wèn)題，也就是NP完全問(wèn)題。此時(shí)，我的目的終于達(dá)到了，我已經(jīng)把NP問(wèn)題和NPC問(wèn)題區(qū)別開(kāi) 了。首先，它得是一個(gè)NP問(wèn)題；然后，所有的NP問(wèn)題都可以約化到它。因此，給NPC找一個(gè)多項(xiàng)式算法太不可思議了。NPHard問(wèn)題是這樣一種 問(wèn)題，它滿足NPC問(wèn)題定義的第二條但不一定要滿足第一條（就是說(shuō)，NPHard問(wèn)題要比 NPC問(wèn)題的范圍廣）。不要以為NPC問(wèn)題是一紙空談。下文即將介紹邏輯電路問(wèn)題。邏輯電路問(wèn)題是指的這樣一個(gè)問(wèn)題：給定一個(gè)邏輯電路，問(wèn)是否存在一種輸入使輸出為T(mén)rue。│輸入1 ├→─┐┌──┐│AND ├─→┐┌─→┤│││└──┘│┌───┐││AND ├─→輸出┌──┐└───┘└→┤NOT ├→──┘回到上文，給定一個(gè)邏輯電路，問(wèn)是否存在一種輸入使輸出為T(mén)rue，這即邏輯電路問(wèn)題。證明過(guò)程相當(dāng)復(fù)雜，其大概意思是說(shuō)任意一個(gè)NP問(wèn)題的輸入和輸出都可以轉(zhuǎn)換成邏輯電路的輸入和輸出（想想計(jì)算機(jī)內(nèi)部也不過(guò)是一些 0和1的運(yùn)算），因此對(duì)于一個(gè)NP問(wèn)題來(lái)說(shuō)，問(wèn)題轉(zhuǎn)化為了求出滿足結(jié)果為T(mén)rue的一個(gè)輸入（即一個(gè)可行解）。因此 說(shuō)，正是因?yàn)镹PC問(wèn)題的存在，P=NP變得難以置信。Matrix67原創(chuàng)轉(zhuǎn)載請(qǐng)注明出處。攀登這個(gè)信息學(xué)的巔峰是我們這一代的 終極目標(biāo)。后來(lái)，Hamilton 回路成了NPC問(wèn)題，TSP問(wèn)題也成了NPC問(wèn)題。這是有嚴(yán)格證明的。上面這個(gè)邏輯電路中，無(wú)論輸入是什么，輸出都是False。└──┘└──┘│┌→┤│輸入2 ├→─┤│└→┤│┌──┐│└─→┤└───┘┌───┐有輸出無(wú)論如何都不可能為T(mén)rue的邏輯電路嗎？有?？聪旅嬉焕?，不需要解釋你馬上就明白了。其它的NPC問(wèn)題都是由這個(gè)問(wèn)題約化而來(lái)的。確實(shí)有這么一個(gè)非常具體的問(wèn)題屬于NPC問(wèn)題。即使NPC問(wèn)題發(fā)現(xiàn)了多項(xiàng)式級(jí) 的算法，NPHard問(wèn)題有可能仍然無(wú)法得到多項(xiàng)式級(jí)的算法。我們可以就此直觀地理解，NPC問(wèn)題 目前沒(méi)有多項(xiàng)式的有效算法，只能用指數(shù)級(jí)甚至階乘級(jí)復(fù)雜度的搜索。先證明它至少是一個(gè)NP問(wèn)題，再證明其中一個(gè)已知的NPC問(wèn)題能約化到它（由約化的傳遞性，則NPC問(wèn)題定義的第二條也得以滿足；至 于第一個(gè)NPC問(wèn)題是怎么來(lái)的，下文將介紹），這樣就可以說(shuō)它是NPC問(wèn)題了。NPC問(wèn)題的定義非常簡(jiǎn) 單。我們有理由相信，NPC問(wèn)題是最復(fù)雜的問(wèn)題。換句話說(shuō)，只要解決了這個(gè)問(wèn)題，那 么所有的NP問(wèn)題都解決了。好 了，從約化的定義中我們看到，一個(gè)問(wèn)題約化為另一個(gè)問(wèn)題，時(shí)間復(fù)雜度增加了，問(wèn)題的應(yīng)用范圍也增大了。這個(gè)道理非常簡(jiǎn)單，就不必闡述了。既然問(wèn)題A能用問(wèn)題B來(lái)解決，倘若B的時(shí)間復(fù)雜度比 A的時(shí)間復(fù)雜度還低了，那A的算法就可以改進(jìn)為B的算法，兩者的時(shí)間復(fù)雜度還是相同。Hamilton回路存在當(dāng)且僅當(dāng)TSP問(wèn)題中存在長(zhǎng)為0的回路。我們可以寫(xiě)出兩個(gè)程序分別對(duì)應(yīng)兩個(gè)問(wèn)題，那么我們能找到一個(gè)“規(guī)則”，按照
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1