什么是p問題、np問題和npc問題-資料下載頁
2025-08-04 13:53本頁面
【正文】 。這是個(gè)較簡(jiǎn)單的邏輯電路，當(dāng)輸入輸入輸入3分別為True、True、False或False、True、False時(shí)，輸出為True。有輸出無論如何都不可能為True的邏輯電路嗎？有。下面就是一個(gè)簡(jiǎn)單的例子。┌───┐│輸入1 ├→─┐┌──┐└───┘└─→┤││AND ├─→┐┌─→┤│││└──┘│┌──┐│└→┤│┌───┐││AND ├─→輸出│輸入2 ├→─┤┌──┐┌→┤│└───┘└→┤NOT ├→──┘└──┘└──┘上面這個(gè)邏輯電路中，無論輸入是什么，輸出都是False。我們就說，這個(gè)邏輯電路不存在使輸出為True的一組輸入。回到上文，給定一個(gè)邏輯電路，問是否存在一種輸入使輸出為True，這即邏輯電路問題。邏 輯電路問題屬于NPC問題。這是有嚴(yán)格證明的。它顯然屬于NP問題，并且可以直接證明所有的NP問題都可以約化到它（不要以為NP問題有無窮多個(gè)將給證明 造成不可逾越的困難）。證明過程相當(dāng)復(fù)雜，其大概意思是說任意一個(gè)NP問題的輸入和輸出都可以轉(zhuǎn)換成邏輯電路的輸入和輸出（想想計(jì)算機(jī)內(nèi)部也不過是一些 0和1的運(yùn)算），因此對(duì)于一個(gè)NP問題來說，問題轉(zhuǎn)化為了求出滿足結(jié)果為True的一個(gè)輸入（即一個(gè)可行解）。有了第一個(gè)NPC 問題后，一大堆NPC問題就出現(xiàn)了，因?yàn)樵僮C明一個(gè)新的NPC問題只需要將一個(gè)已知的NPC問題約化到它就行了。后來，Hamilton 回路成了NPC問題，TSP問題也成了NPC問題?，F(xiàn)在被證明是NPC問題的有很多，任何一個(gè)找到了多項(xiàng)式算法的話所有的NP問題都可以完美解決了。因此 說，正是因?yàn)镹PC問題的存在，P=NP變得難以置信。P=NP問題還有許多有趣的東西，有待大家自己進(jìn)一步的挖掘。攀登這個(gè)信息學(xué)的巔峰是我們這一代的 終極目標(biāo)?，F(xiàn)在我們需要做的，至少是不要把概念弄混淆了。Matrix67原創(chuàng)轉(zhuǎn)載請(qǐng)注明出處
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1