那傳說(shuō)中的P、NP以及NPC問(wèn)題

? ? （這里只是自己的一些總結(jié)）

? ? ?在講這幾個(gè)問(wèn)題之前，有幾個(gè)東西是必須要說(shuō)的，包括時(shí)間復(fù)雜度、空間復(fù)雜度、圖靈機(jī)什么的。那么我們就慢慢來(lái)一一說(shuō)來(lái)。

????? ?圖靈機(jī)：圖靈機(jī)其實(shí)就是一個(gè)計(jì)算模型，是由圖靈提出來(lái)的。圖靈機(jī)號(hào)稱可以模擬實(shí)際計(jì)算機(jī)的所有計(jì)算行為，計(jì)算能力還超過(guò)現(xiàn)有的計(jì)算機(jī)。但是還是有圖靈機(jī)無(wú)法做到的事情，就好像計(jì)算機(jī)并不能處理所有的事情一樣。

????? 定義：

???????1）有一個(gè)無(wú)限長(zhǎng)的帶子作為無(wú)限存儲(chǔ)。

?????? 2）有一個(gè)讀寫(xiě)頭，能在帶子上讀、寫(xiě)和左右移動(dòng)。

?????? 3）有一套控制規(guī)則，根據(jù)當(dāng)前機(jī)器所處的狀態(tài)以及當(dāng)前讀寫(xiě)頭所指的格子符號(hào)來(lái)確定下一步的動(dòng)作，另機(jī)器進(jìn)入一個(gè)新的狀態(tài)。

??????4）一個(gè)狀態(tài)寄存器，用來(lái)保存圖靈機(jī)當(dāng)前所處的狀態(tài)。

? ? ? 工作方式：

? ? ? 在圖靈機(jī)的計(jì)算過(guò)程中，當(dāng)前狀態(tài)、當(dāng)前帶內(nèi)容和讀寫(xiě)頭當(dāng)前位置組合一起稱為圖靈機(jī)的格局。包括起始格局、接受格局、拒絕格局。

? ? ? 圖靈機(jī)讀取紙袋上的內(nèi)容，結(jié)合讀寫(xiě)頭的當(dāng)前狀態(tài)，根據(jù)一組控制規(guī)則決定下一步的動(dòng)作?？梢哉J(rèn)為這是一臺(tái)理想的，能夠處理所有的“人類計(jì)算”。

?

? ? ? ?我們可以想象，一個(gè)問(wèn)題如果在理論上是可解的，但是計(jì)算它所需要的時(shí)間和空間的資源是我們無(wú)法承受的，那么這個(gè)問(wèn)題對(duì)我們來(lái)說(shuō)就是沒(méi)有用的。當(dāng)然這里說(shuō)明一個(gè)問(wèn)題是否理論上可解，用到圖靈機(jī)什么的一籮筐東西，這里就不說(shuō)明這些問(wèn)題。

? ? ?時(shí)間復(fù)雜度：?對(duì)于一個(gè)算法的時(shí)間復(fù)雜度一般采用大O表示，這里大O我就具體說(shuō)明了，就是說(shuō)明一個(gè)算法的時(shí)間復(fù)雜度的函數(shù)O(t（n))。運(yùn)行時(shí)間是多項(xiàng)式時(shí)間的算法隨著問(wèn)題規(guī)模的不斷上升，時(shí)間變化不大，但是如果一個(gè)算法的時(shí)間是指數(shù)形式的話，就不可理喻了。典型的指數(shù)時(shí)間算法源于通過(guò)搜索解空間來(lái)求解問(wèn)題，這稱為蠻力搜索。當(dāng)然很多算法可以通過(guò)一些技巧避免蠻力搜索，但是還是有一些問(wèn)題，我們是無(wú)能為力的，至今沒(méi)有找到在多項(xiàng)式時(shí)間求解該問(wèn)題的算法。

? ? ?P類問(wèn)題：

? ?? ?簡(jiǎn)單的認(rèn)為，P問(wèn)題就是可以在多項(xiàng)式時(shí)間被圖靈機(jī)判定的語(yǔ)言類。這里又涉及到圖靈機(jī)，那么我們可以簡(jiǎn)單的認(rèn)為，如果一個(gè)算法可以在多項(xiàng)式時(shí)間內(nèi)求解，那么就可以認(rèn)為它是P類問(wèn)題。這樣你就會(huì)感覺(jué)好多算法都是P類問(wèn)題，對(duì)！沒(méi)錯(cuò)！如何證明一個(gè)問(wèn)題是否是P類問(wèn)題呢？只要它滿足以下兩個(gè)條（證明它在多項(xiàng)式時(shí)間內(nèi)完成）

? ? ? 1）運(yùn)行步驟數(shù)要有多項(xiàng)式上屆時(shí)間

? ? ? 2）每一步都要保證它可以由合理的確定模型在多項(xiàng)式時(shí)間內(nèi)完成，其實(shí)就是每一步的求解過(guò)程也是多項(xiàng)式時(shí)間

? ? ? 這樣步奏是多項(xiàng)式時(shí)間的，而每一步也是多項(xiàng)式時(shí)間，整合起來(lái)整個(gè)算法還是多項(xiàng)式時(shí)間的。

? ? ? 想PATH問(wèn)題就是屬于P

? ? ?PATH的一個(gè)多項(xiàng)式時(shí)間算法M運(yùn)行如下：

? ? ?M="對(duì)于輸入<G,s,t>,G是包含結(jié)點(diǎn)s和t的有向圖：

? ? ? ? ? （1）在結(jié)點(diǎn)s上做標(biāo)記。

? ? ? ? ? （2）重復(fù)下面步驟3，直到不再有結(jié)點(diǎn)被標(biāo)記。

? ? ? ? ? （3）掃描G的所有邊，如果找到一條邊（a,b），a被標(biāo)記而b沒(méi)有，那么標(biāo)記b

? ? ? ? ? （4）若t被標(biāo)記，則接受否則拒絕"

? ?分析上面算法，可以得到步奏1和4只執(zhí)行1步，步驟3最多執(zhí)行m次，所以用到的步驟數(shù)是m+1+1。每一步都可以在合理的多項(xiàng)式時(shí)間內(nèi)完成，所有PATH是P類問(wèn)題。

?NP類問(wèn)題：

? ? ? 這里NP并不是指Not P的意思！實(shí)際上P是屬于NP的，但是NP是否等于P我們目前還不懂。

? ? ?NP問(wèn)題指的是，這個(gè)算法可以在多項(xiàng)式時(shí)間內(nèi)可驗(yàn)證，什么意思呢？我們知道對(duì)于P類問(wèn)題，可以在多項(xiàng)式時(shí)間內(nèi)求解出來(lái)，但是NP問(wèn)題不行?？梢赃@樣理解，NP雖然不能在多項(xiàng)式時(shí)間內(nèi)被求解，但是如果給出這個(gè)問(wèn)題的某個(gè)解，那么我們可以在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證這個(gè)解是不是這個(gè)問(wèn)題的解。聽(tīng)起來(lái)好像有點(diǎn)那這有什么用的感覺(jué)？比如求漢密爾頓路徑問(wèn)題（HAMPATH），我們只能在指數(shù)時(shí)間內(nèi)求出這個(gè)解，但是這時(shí)候我們假設(shè)我們可以先隨機(jī)猜測(cè)出一條路徑序列出來(lái)，那么我們就可在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證這個(gè)解是不是對(duì)的。常常也稱為非確定型多項(xiàng)式時(shí)間。

?

簡(jiǎn)單的的區(qū)分P和NP問(wèn)題：

? ? ?對(duì)于P問(wèn)題，我們可以有個(gè)算法能夠在多項(xiàng)式時(shí)間內(nèi)求得解。但是對(duì)于NP問(wèn)題，就不可以了，求解某個(gè)問(wèn)題可能需要指數(shù)的時(shí)間。NP問(wèn)題也可以認(rèn)為，我們可以在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證一個(gè)解，比如說(shuō)我可以隨機(jī)猜測(cè)一個(gè)解，如果我可以在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證說(shuō)明這個(gè)解是不是問(wèn)題的解，那么這個(gè)問(wèn)題就是NP問(wèn)題。

?

?NPC類問(wèn)題：

? ? ?說(shuō)到NP完全問(wèn)題，那么就需要說(shuō)到可規(guī)約這個(gè)問(wèn)題。

? ? ?規(guī)約：當(dāng)問(wèn)題A規(guī)約到B問(wèn)題時(shí)，B的有效解就可以用于求解問(wèn)題A了。

? ? NPC指定是所有的NP問(wèn)題都可以多項(xiàng)式時(shí)間規(guī)約到某一類問(wèn)題，那么這某一類問(wèn)題就是所謂的NPC問(wèn)題。

?

?

?

?

? ??

轉(zhuǎn)載于:https://www.cnblogs.com/GuoJiaSheng/p/4231094.html

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的那传说中的P、NP以及NPC问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。