在研究NP問題的過程中找到了一類非常特殊的NP問題唱凯，也即NP-完全問題(NP-C問題)。
在談及NPC問題前霍骄，先討論一下“歸約”的概念畅铭，編碼實踐中歸納出的設(shè)計模式中的里氏替換原則與它有著相似的地方。
里氏替換原則要求充分發(fā)揮繼承的特性：
1兵琳、子類必須完全實現(xiàn)父類的方法
2狂秘、子類可以有自己的個性
3、覆寫或?qū)崿F(xiàn)父類方法時輸入?yún)?shù)可以被放大
4躯肌、覆寫或?qū)崿F(xiàn)父類方法時輸出結(jié)果可以被縮小
在可計算性理論與計算復雜性理論中者春，所謂的歸約是將某個計算問題轉(zhuǎn)換為另一個問題的過程∏迮可用歸約的方法定義某些問題的復雜度類钱烟。即如果問題B存在有效的解決算法，并且該算法也可以作為解決問題A的算法，那么問題A就可歸約到問題B拴袭，因此求解問題A不會比問題B的求解更困難读第。
當問題A可歸約為問題B時，有一個直觀的意義就是拥刻，問題B的時間復雜度高于或者等于問題A的時間復雜度怜瞒。為什么這么說呢？
如果問題A能用問題B的算法解決泰佳，并且問題A的時間復雜度還比問題B的時間復雜度高盼砍，那么問題A的算法就可以改進為B算法，這樣兩者的時間復雜度就是相等的逝她，所以有了上面的“直觀意義”。
正如解一元二次方程比解一元一次方程難睬捶，因為解決前者的方法可以用來解決后者黔宛。即一元一次方程可歸約為一元二次方程。
規(guī)約的標準概念：如果能找到這樣一個變化法則擒贸，對任意一個程序A的輸入臀晃，都能按照這個法則變換成程序B的輸入，使兩程序的輸出相同介劫，那么我們說問題A可歸約為問題B徽惋。我們所說的“可歸約”是指可多項式的約化，即變換輸入的方法座韵，問題的解決也是在多項式時間內(nèi)解決的险绘，只有這樣才是有意義的。
可以看到誉碴，一個問題約化為另一個問題宦棺，時間復雜度增加了，問題的應用范圍也增加了黔帕。通過對某些問題的不斷約化代咸，能夠不斷地尋找時間復雜度更高，但應用范圍更廣的一類問題的算法去替代時間復雜度低成黄，但只能用于很小的一類問題的算法呐芥。
同時因為約化具有傳遞性，很容易想到對于所有的NP問題奋岁，能否最后歸約到一個超級大的NP問題思瘟？解決了這個超級NP問題，那么所有的NP問題都能得到解答厦取。問題的答案居然是肯定的潮太，更加不可思議的是，這種超級NP問題不止一個，它有很多铡买，它們是一類問題更鲁，這類問題就是NPC問題。
NPC問題的出現(xiàn)使得整個NP問題的研究得到了飛躍式的發(fā)展奇钞，我們有理由相信NPC問題是最復雜的NP問題澡为。
如果能為任意一個NPC問題找到一個多項式的高效算法，我們就可以認為P=NP景埃，就是因為那么多的NPC的問題至今沒有一個問題能找到一個多項式的算法媒至，使得人們普遍認為P≠NP。
更直觀的講什么是NPC問題：一個NP問題不存在多項式的高效算法時谷徙，應該說它可能屬于NPC問題拒啰。為什么這樣講？因為NPC問題的第二個條件不被滿足完慧，第二個條件是什么后面會說到谋旦。
假使一個NPC問題存在一個多項式的高效算法時，即所有的NP問題都可以找到了一個多項式的高效算法屈尼，那么這個問題變成了P問題册着，那么P=NP。
關(guān)于NPC問題的定義需要滿足下面兩個條件：1脾歧、它是一個NP問題甲捏。 2、所有的NP問題都可以約化到它鞭执。要證明一個問題是NPC問題司顿，先證明這個問題屬于NP問題，再證明一個已知的NPC問題可以約化到它蚕冬。這樣就可以說它是NPC問題了免猾。那么第一個已知的NPC問題是怎么來的呢？
邏輯電路問題是第一個NPC問題囤热，它是這樣描述的：給定一個邏輯電路猎提，問是否存在一種輸入使輸出為True。
條件一：對邏輯電路給定一種輸入旁蔼，可以在多項式時間內(nèi)進行驗證锨苏，所以屬于NP問題。
當輸入1棺聊、輸入2伞租、輸入3分別輸入true、true限佩、false或false葵诈、true裸弦、false或true、false作喘、false時輸出為true
有輸入無論如何都不會為true的邏輯電路嘛理疙？有的
上面的邏輯電路無論輸入什么，輸出總為false,
邏輯電路屬于NPC問題是有嚴格的證明的泞坦。首先它是屬于NP問題的窖贤，對給定的一個輸入可以在多項式的時間內(nèi)進行驗證。其次也可以證明所有的NP問題都能約化到它贰锁，不要認為NP問題有無窮多個將給證明造成不可逾越的困難赃梧，證明過程相當復雜，大概意思是講豌熄，任意一個NP問題的輸入和輸出都可以轉(zhuǎn)換為邏輯電路的輸入和輸出（計算機內(nèi)部的0 1運算）授嘀，因此對于一個NP問題來說，問題轉(zhuǎn)化為了求滿足結(jié)果為True的一個輸入（即一個可行解）锣险。
有了第一個NPC問題粤攒，一大堆NPC問題就出現(xiàn)了，后來Hamilton回路問題成了NPC問題囱持，TSP問題也成為了NPC問題，這么多NPC問題焕济，任何一個NPC問題找到了多項式算法的話纷妆，我們就說P=NP，也正是因為NPC問題的存在使得P=NP變得難以置信晴弃。掩幢！
