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