什么是p問(wèn)題、np問(wèn)題和npc問(wèn)題(參考版)
2024-08-16 18:58本頁(yè)面
【正文】 Matrix67原創(chuàng)轉(zhuǎn)載請(qǐng)注明出處。攀登這個(gè)信息學(xué)的巔峰是我們這一代的 終極目標(biāo)。因此 說(shuō)，正是因?yàn)镹PC問(wèn)題的存在，P=NP變得難以置信。后來(lái)，Hamilton 回路成了NPC問(wèn)題，TSP問(wèn)題也成了NPC問(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è)可行解）。這是有嚴(yán)格證明的?；氐缴衔?，給定一個(gè)邏輯電路，問(wèn)是否存在一種輸入使輸出為T(mén)rue，這即邏輯電路問(wèn)題。上面這個(gè)邏輯電路中，無(wú)論輸入是什么，輸出都是False。└──┘└──┘└→┤NOT ├→──┘└───┘│┌→┤┌──┐│輸入2 ├→─┤│AND ├─→輸出│┌───┐│└→┤│┌──┐│└──┘│││┌─→┤│AND ├─→┐│└─→┤└───┘┌──┐│輸入1 ├→─┐┌───┐有輸出無(wú)論如何都不可能為T(mén)rue的邏輯電路嗎？有?？聪旅嬉焕?，不需要解釋你馬上就明白了。邏輯電路問(wèn)題是指的這樣一個(gè)問(wèn)題：給定一個(gè)邏輯電路，問(wèn)是否存在一種輸入使輸出為T(mén)rue。其它的NPC問(wèn)題都是由這個(gè)問(wèn)題約化而來(lái)的。下文即將介紹邏輯電路問(wèn)題。確實(shí)有這么一個(gè)非常具體的問(wèn)題屬于NPC問(wèn)題。不要以為NPC問(wèn)題是一紙空談。即使NPC問(wèn)題發(fā)現(xiàn)了多項(xiàng)式級(jí) 的算法，NPHard問(wèn)題有可能仍然無(wú)法得到多項(xiàng)式級(jí)的算法。NPHard問(wèn)題是這樣一種 問(wèn)題，它滿足NPC問(wèn)題定義的第二條但不一定要滿足第一條（就是說(shuō)，NPHard問(wèn)題要比 NPC問(wèn)題的范圍廣）。我們可以就此直觀地理解，NPC問(wèn)題 目前沒(méi)有多項(xiàng)式的有效算法，只能用指數(shù)級(jí)甚至階乘級(jí)復(fù)雜度的搜索。因此，給NPC找一個(gè)多項(xiàng)式算法太不可思議了。先證明它至少是一個(gè)NP問(wèn)題，再證明其中一個(gè)已知的NPC問(wèn)題能約化到它（由約化的傳遞性，則NPC問(wèn)題定義的第二條也得以滿足；至 于第一個(gè)NPC問(wèn)題是怎么來(lái)的，下文將介紹），這樣就可以說(shuō)它是NPC問(wèn)題了。首先，它得是一個(gè)NP問(wèn)題；然后，所有的NP問(wèn)題都可以約化到它。NPC問(wèn)題的定義非常簡(jiǎn) 單。此時(shí)，我的目的終于達(dá)到了，我已經(jīng)把NP問(wèn)題和NPC問(wèn)題區(qū)別開(kāi) 了。我們有理由相信，NPC問(wèn)題是最復(fù)雜的問(wèn)題。這一類問(wèn)題就是傳說(shuō)中的NPC 問(wèn)題，也就是NP完全問(wèn)題。換句話說(shuō)，只要解決了這個(gè)問(wèn)題，那 么所有的NP問(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)題？答案居然是肯定的。好 了，從約化的定義中我們看到，一個(gè)問(wèn)題約化為另一個(gè)問(wèn)題，時(shí)間復(fù)雜度增加了，問(wèn)題的應(yīng)用范圍也增大了。當(dāng)然，我們所說(shuō)的“可約化”是指的可“多項(xiàng)式地”約化(Polynomialtime Reducible)，即變換輸入的方法是能在多項(xiàng)式的時(shí)間里完成的
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1