在一本關(guān)于數(shù)據(jù)結(jié)構(gòu)的書末尾提到了NP完全問題旋廷，毫無概念。因此做一番搜索和整理礼搁，便于反復(fù)閱讀和理解饶碘。
百度百科的摘錄
NP完全問題(NP-C問題)，是世界七大數(shù)學(xué)難題之一叹坦。 NP的英文全稱是Non-deterministic Polynomial的問題熊镣，即多項式復(fù)雜程度的非確定性問題。簡單的寫法是 NP=P募书？绪囱，問題就在這個問號上，到底是NP等于P莹捡，還是NP不等于P鬼吵。
詳細(xì)信息
P類問題：所有可以在多項式時間內(nèi)求解的判定問題構(gòu)成P類問題篮赢。**判定問題****：判斷是否有一種能夠解決某一類問題的能行算法的研究課題。
NP類問題：所有的非確定性多項式時間可解的判定問題構(gòu)成NP類問題启泣。非確定性算法：非確定性算法將問題分解成猜測和驗證兩個階段涣脚。算法的猜測階段是非確定性的寥茫，算法的驗證階段是確定性的，它驗證猜測階段給出解的正確性。設(shè)算法A是解一個判定問題Q的非確定性算法芭梯，如果A的驗證階段能在多項式時間內(nèi)完成，則稱A是一個多項式時間非確定性算法玖喘。有些計算問題是確定性的甩牺，例如加減乘除累奈，只要按照公式推導(dǎo)贬派，按部就班一步步來，就可以得到結(jié)果费尽。但是赠群，有些問題是無法按部就班直接地計算出來。比如旱幼，找大質(zhì)數(shù)的問題查描。有沒有一個公式能推出下一個質(zhì)數(shù)是多少呢？這種問題的答案柏卤，是無法直接計算得到的冬三，只能通過間接的“猜算”來得到結(jié)果。這也就是非確定性問題缘缚。而這些問題的通常有個算法勾笆，它不能直接告訴你答案是什么，但可以告訴你桥滨，某個可能的結(jié)果是正確的答案還是錯誤的窝爪。這個可以告訴你“猜算”的答案正確與否的算法，假如可以在多項式（polynomial）時間內(nèi)算出來齐媒，就叫做多項式非確定性問題蒲每。
NPC問題：NP中的某些問題的復(fù)雜性與整個類的復(fù)雜性相關(guān)聯(lián).這些問題中任何一個如果存在多項式時間的算法,那么所有NP問題都是多項式時間可解的.這些問題被稱為NP-完全問題(NPC問題)。
舉例敘述
在一個周六的晚上喻括，你參加了一個盛大的晚會邀杏。由于感到局促不安，你想知道這一大廳中是否有你已經(jīng)認(rèn)識的人唬血。你的主人向你提議說望蜡，你一定認(rèn)識那位正在甜點盤附近角落的女士羅絲。不費一秒鐘拷恨，你就能向那里掃視脖律，并且發(fā)現(xiàn)你的主人是正確的。然而腕侄，如果沒有這樣的暗示小泉，你就必須環(huán)顧整個大廳勒叠，一個個地審視每一個人，看是否有你認(rèn)識的人膏孟。
生成問題的一個解通常比驗證一個給定的解時間花費要多得多。這是這種一般現(xiàn)象的一個例子拌汇。與此類似的是柒桑，如果某人告訴你，數(shù)13,717,421可以寫成兩個較小的數(shù)的乘積噪舀，你可能不知道是否應(yīng)該相信他魁淳，但是如果他告訴你他可以因式分解為3607乘上3803，那么你就可以用一個袖珍計算器容易驗證這是對的与倡。人們發(fā)現(xiàn)界逛，所有的完全多項式非確定性問題，都可以轉(zhuǎn)換為一類叫做滿足性問題的邏輯運算問題纺座。既然這類問題的所有可能答案息拜，都可以在多項式時間內(nèi)計算净响，人們于是就猜想，是否這類問題馋贤，存在一個確定性算法，可以在多項式時間內(nèi)仿滔，直接算出或是搜尋出正確的答案呢？這就是著名的NP=P崎页？的猜想羽莺。 不管我們編寫程序是否靈巧实昨，判定一個答案是可以很快利用內(nèi)部知識來驗證荒给，還是沒有這樣的提示而需要花費大量時間來求解，被看作邏輯和計算機(jī)科學(xué)中最突出的問題之一志电。它是斯蒂文·考克于1971年陳述的蛔趴。
看到概念中有一個 多項式復(fù)雜度，會影響對NP問題的理解。在知乎上找到一篇 知乎老抽 Club的解釋鱼蝉。
首先知道多項式嗎？也就是對于變量n魁亦，5n2+2n+1這種就叫做多項式。前面再加上n3甚至一路增加到nm洁奈，只要m是個常量，就都是多項式呈野。因為這樣的式子合并同類項什么的簡化到最后還是會有好幾個含n的項，所以叫做多項式被冒。然后再說問題大小n。其實字面理解就對了…也就是說姆打，我們要解決一個問題肠虽，這個問題里面有n個“東西”要處理，這個問題的大小就是n税课。比方說，我們要把5韩玩、7、9這三個數(shù)字排序找颓，問題大小就是3。我們要把全世界人類里面的男的找出來佛析，問題大小就是全世界人口數(shù)。然后是多項式倍數(shù)彪蓬。這個倍數(shù)是指，對于一個變量n膘茎，有這樣一個倍數(shù)桃纯，它的值是n的一個多項式态坦。比方說，我們假設(shè)n=5驮配，那么n2+10=52+10=35，這個35就是n的一個多項式倍數(shù)。因為對于n有無限多種多項式組合琐旁，所以它也就有無窮多個多項式倍數(shù)。多項式倍數(shù)之所以特殊灰殴，主要是由于其值隨n增大而加速增大的特性。如果是常數(shù)時間的話伟阔，意思就是無論n是什么值運算所花時間都一樣。線性時間則是說多大n就花多少時間皱炉。多項式時間則意味著隨著n增大狮鸭，n每增加1所花的時間增長越來越多。對于n2-3這樣一個多項式時間來說歧蕉，n=2的時候可能只要花1的時間，甚至低于線性時間惯退，但n=4的時候可能就要花13的時間了，可以想象再大一些這個數(shù)值會變得巨大锁蠕。但是它又不及指數(shù)時間增長快(mn)，且mn不能寫成多項式形式懊蒸，所以它又和多項式時間有區(qū)別。而且逃呼，這個增長變速的特性是不受參數(shù)限制的。也就是說抡笼，無論你把m*n^2的m這個常量改成多么微小的一個值苏揣，總有一個n讓這個多項式的值大于n平匈，也就是說到這一刻多項式時間的算法耗時高于了線性時間的算法藏古，之后耗時差距一定會越來越大。這一特性是多項式本身的性質(zhì)決定的拧晕。類似，指數(shù)級時間也是如此厂捞，無論你將n的一個多項式中的所有常量設(shè)置到多大，總有一個n的指數(shù)值大于多項式值欲鹏。所以我們說指數(shù)時間大于多項式時間，我們說多項式時間大于線性時間臭墨，我們還說線性時間大于常數(shù)時間，一定要注意這些大于并不是對于所有n的所有情況成立的尽狠，只是在說隨著n增加前者一定超過后者。希望有幫助袄膏。
至此對NP完全問題掺冠，能有一知半解。后續(xù)在深入學(xué)習(xí)實踐
