什么是p問題、np問題和npc問題(參考版)
2024-08-15 13:53本頁面
【正文】 Matrix67原創(chuàng)轉(zhuǎn)載請(qǐng)注明出處。攀登這個(gè)信息學(xué)的巔峰是我們這一代的 終極目標(biāo)。因此 說，正是因?yàn)镹PC問題的存在，P=NP變得難以置信。后來，Hamilton 回路成了NPC問題，TSP問題也成了NPC問題。證明過程相當(dāng)復(fù)雜，其大概意思是說任意一個(gè)NP問題的輸入和輸出都可以轉(zhuǎn)換成邏輯電路的輸入和輸出（想想計(jì)算機(jī)內(nèi)部也不過是一些 0和1的運(yùn)算），因此對(duì)于一個(gè)NP問題來說，問題轉(zhuǎn)化為了求出滿足結(jié)果為True的一個(gè)輸入（即一個(gè)可行解）。這是有嚴(yán)格證明的?；氐缴衔?，給定一個(gè)邏輯電路，問是否存在一種輸入使輸出為True，這即邏輯電路問題。上面這個(gè)邏輯電路中，無論輸入是什么，輸出都是False。└──┘└──┘└→┤NOT ├→──┘└───┘│┌→┤┌──┐│輸入2 ├→─┤│AND ├─→輸出│┌───┐│└→┤│┌──┐│└──┘│││┌─→┤│AND ├─→┐│└─→┤└───┘┌──┐│輸入1 ├→─┐┌───┐有輸出無論如何都不可能為True的邏輯電路嗎？有?？聪旅嬉焕恍枰忉屇泷R上就明白了。邏輯電路問題是指的這樣一個(gè)問題：給定一個(gè)邏輯電路，問是否存在一種輸入使輸出為True。其它的NPC問題都是由這個(gè)問題約化而來的。下文即將介紹邏輯電路問題。確實(shí)有這么一個(gè)非常具體的問題屬于NPC問題。不要以為NPC問題是一紙空談。即使NPC問題發(fā)現(xiàn)了多項(xiàng)式級(jí) 的算法，NPHard問題有可能仍然無法得到多項(xiàng)式級(jí)的算法。NPHard問題是這樣一種 問題，它滿足NPC問題定義的第二條但不一定要滿足第一條（就是說，NPHard問題要比 NPC問題的范圍廣）。我們可以就此直觀地理解，NPC問題 目前沒有多項(xiàng)式的有效算法，只能用指數(shù)級(jí)甚至階乘級(jí)復(fù)雜度的搜索。因此，給NPC找一個(gè)多項(xiàng)式算法太不可思議了。先證明它至少是一個(gè)NP問題，再證明其中一個(gè)已知的NPC問題能約化到它（由約化的傳遞性，則NPC問題定義的第二條也得以滿足；至 于第一個(gè)NPC問題是怎么來的，下文將介紹），這樣就可以說它是NPC問題了。首先，它得是一個(gè)NP問題；然后，所有的NP問題都可以約化到它。NPC問題的定義非常簡(jiǎn) 單。此時(shí)，我的目的終于達(dá)到了，我已經(jīng)把NP問題和NPC問題區(qū)別開 了。我們有理由相信，NPC問題是最復(fù)雜的問題。這一類問題就是傳說中的NPC 問題，也就是NP完全問題。換句話說，只要解決了這個(gè)問題，那 么所有的NP問題都解決了。再回想前面講的P和NP問題，聯(lián)想起約化的傳遞性，自然地，我們會(huì)想 問，如果不斷地約化上去，不斷找到能“通吃”若干小NP問題的一個(gè)稍復(fù)雜的大NP問題，那么最后是否有可能找到一個(gè)時(shí)間復(fù)雜度最高，并且能“通吃”所有的 NP問題的這樣一個(gè)超級(jí)NP問題？答案居然是肯定的。好 了，從約化的定義中我們看到，一個(gè)問題約化為另一個(gè)問題，時(shí)間復(fù)雜度增加了，問題的應(yīng)用范圍也增大了。當(dāng)然，我們所說的“可約化”是指的可“多項(xiàng)式地”約化(Polynomialtime Reducible)，即變換輸入的方法是能在多項(xiàng)式的時(shí)間里完成的
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1