在研究NP問題的過程中找到了一類非常特殊的NP問題，也即NP-完全問題(NP-C問題)。
在談及NPC問題前，先討論一下“歸約”的概念，編碼實(shí)踐中歸納出的設(shè)計(jì)模式中的里氏替換原則與它有著相似的地方。
里氏替換原則要求充分發(fā)揮繼承的特性：
1、子類必須完全實(shí)現(xiàn)父類的方法
2、子類可以有自己的個(gè)性
3、覆寫或?qū)崿F(xiàn)父類方法時(shí)輸入?yún)?shù)可以被放大
4、覆寫或?qū)崿F(xiàn)父類方法時(shí)輸出結(jié)果可以被縮小
在可計(jì)算性理論與計(jì)算復(fù)雜性理論中，所謂的歸約是將某個(gè)計(jì)算問題轉(zhuǎn)換為另一個(gè)問題的過程?？捎脷w約的方法定義某些問題的復(fù)雜度類。即如果問題B存在有效的解決算法，并且該算法也可以作為解決問題A的算法，那么問題A就可歸約到問題B，因此求解問題A不會比問題B的求解更困難。
當(dāng)問題A可歸約為問題B時(shí)，有一個(gè)直觀的意義就是，問題B的時(shí)間復(fù)雜度高于或者等于問題A的時(shí)間復(fù)雜度。為什么這么說呢？
如果問題A能用問題B的算法解決，并且問題A的時(shí)間復(fù)雜度還比問題B的時(shí)間復(fù)雜度高，那么問題A的算法就可以改進(jìn)為B算法，這樣兩者的時(shí)間復(fù)雜度就是相等的，所以有了上面的“直觀意義”。
正如解一元二次方程比解一元一次方程難，因?yàn)榻鉀Q前者的方法可以用來解決后者。即一元一次方程可歸約為一元二次方程。
規(guī)約的標(biāo)準(zhǔn)概念：如果能找到這樣一個(gè)變化法則，對任意一個(gè)程序A的輸入，都能按照這個(gè)法則變換成程序B的輸入，使兩程序的輸出相同，那么我們說問題A可歸約為問題B。我們所說的“可歸約”是指可多項(xiàng)式的約化，即變換輸入的方法，問題的解決也是在多項(xiàng)式時(shí)間內(nèi)解決的，只有這樣才是有意義的。
可以看到，一個(gè)問題約化為另一個(gè)問題，時(shí)間復(fù)雜度增加了，問題的應(yīng)用范圍也增加了。通過對某些問題的不斷約化，能夠不斷地尋找時(shí)間復(fù)雜度更高，但應(yīng)用范圍更廣的一類問題的算法去替代時(shí)間復(fù)雜度低，但只能用于很小的一類問題的算法。
同時(shí)因?yàn)榧s化具有傳遞性，很容易想到對于所有的NP問題，能否最后歸約到一個(gè)超級大的NP問題？解決了這個(gè)超級NP問題，那么所有的NP問題都能得到解答。問題的答案居然是肯定的，更加不可思議的是，這種超級NP問題不止一個(gè)，它有很多，它們是一類問題，這類問題就是NPC問題。
NPC問題的出現(xiàn)使得整個(gè)NP問題的研究得到了飛躍式的發(fā)展，我們有理由相信NPC問題是最復(fù)雜的NP問題。
如果能為任意一個(gè)NPC問題找到一個(gè)多項(xiàng)式的高效算法，我們就可以認(rèn)為P=NP，就是因?yàn)槟敲炊嗟腘PC的問題至今沒有一個(gè)問題能找到一個(gè)多項(xiàng)式的算法，使得人們普遍認(rèn)為P≠NP。
更直觀的講什么是NPC問題：一個(gè)NP問題不存在多項(xiàng)式的高效算法時(shí)，應(yīng)該說它可能屬于NPC問題。為什么這樣講？因?yàn)镹PC問題的第二個(gè)條件不被滿足，第二個(gè)條件是什么后面會說到。
假使一個(gè)NPC問題存在一個(gè)多項(xiàng)式的高效算法時(shí)，即所有的NP問題都可以找到了一個(gè)多項(xiàng)式的高效算法，那么這個(gè)問題變成了P問題，那么P=NP。
關(guān)于NPC問題的定義需要滿足下面兩個(gè)條件：1、它是一個(gè)NP問題。 2、所有的NP問題都可以約化到它。要證明一個(gè)問題是NPC問題，先證明這個(gè)問題屬于NP問題，再證明一個(gè)已知的NPC問題可以約化到它。這樣就可以說它是NPC問題了。那么第一個(gè)已知的NPC問題是怎么來的呢？
邏輯電路問題是第一個(gè)NPC問題，它是這樣描述的：給定一個(gè)邏輯電路，問是否存在一種輸入使輸出為True。
條件一：對邏輯電路給定一種輸入，可以在多項(xiàng)式時(shí)間內(nèi)進(jìn)行驗(yàn)證，所以屬于NP問題。
當(dāng)輸入1、輸入2、輸入3分別輸入true、true、false或false、true、false或true、false、false時(shí)輸出為true
有輸入無論如何都不會為true的邏輯電路嘛？有的
上面的邏輯電路無論輸入什么，輸出總為false,
邏輯電路屬于NPC問題是有嚴(yán)格的證明的。首先它是屬于NP問題的，對給定的一個(gè)輸入可以在多項(xiàng)式的時(shí)間內(nèi)進(jìn)行驗(yàn)證。其次也可以證明所有的NP問題都能約化到它，不要認(rèn)為NP問題有無窮多個(gè)將給證明造成不可逾越的困難，證明過程相當(dāng)復(fù)雜，大概意思是講，任意一個(gè)NP問題的輸入和輸出都可以轉(zhuǎn)換為邏輯電路的輸入和輸出（計(jì)算機(jī)內(nèi)部的0 1運(yùn)算），因此對于一個(gè)NP問題來說，問題轉(zhuǎn)化為了求滿足結(jié)果為True的一個(gè)輸入（即一個(gè)可行解）。
有了第一個(gè)NPC問題，一大堆NPC問題就出現(xiàn)了，后來Hamilton回路問題成了NPC問題，TSP問題也成為了NPC問題，這么多NPC問題，任何一個(gè)NPC問題找到了多項(xiàng)式算法的話，我們就說P=NP，也正是因?yàn)镹PC問題的存在使得P=NP變得難以置信。！
