（今日上課提到NPC問題籽腕，查之爱葵，得一文章施戴，愿與諸位分享）
##Matrix67原創(chuàng)##
? ? 這或許是眾多OIer最大的誤區(qū)之一反浓。
? ? 你會經(jīng)常看到網(wǎng)上出現(xiàn)“這怎么做赞哗，這不是NP問題嗎”雷则、“這個只有搜了，這已經(jīng)被證明是NP問題了”之類的話肪笋。你要知道月劈，大多數(shù)人此時所說的NP問題其實都是指的NPC問題。他們沒有搞清楚NP問題和NPC問題的概念涂乌。NP問題并不是那種“只有搜才行”的問題艺栈，NPC問題才是。好湾盒，行了湿右，基本上這個誤解已經(jīng)被澄清了。下面的內(nèi)容都是在講什么是P問題罚勾，什么是NP問題毅人，什么是NPC問題，你如果不是很感興趣就可以不看了尖殃。接下來你可以看到丈莺，把NP問題當成是 NPC問題是一個多大的錯誤。
? ? 還是先用幾句話簡單說明一下時間復(fù)雜度送丰。時間復(fù)雜度并不是表示一個程序解決問題需要花多少時間缔俄，而是當問題規(guī)模擴大后，程序需要的時間長度增長得有多快器躏。也就是說俐载，對于高速處理數(shù)據(jù)的計算機來說，處理某一個特定數(shù)據(jù)的效率不能衡量一個程序的好壞登失，而應(yīng)該看當這個數(shù)據(jù)的規(guī)模變大到數(shù)百倍后遏佣，程序運行時間是否還是一樣，或者也跟著慢了數(shù)百倍揽浙，或者變慢了數(shù)萬倍状婶。不管數(shù)據(jù)有多大，程序處理花的時間始終是那么多的馅巷，我們就說這個程序很好膛虫，具有O(1)的時間復(fù)雜度，也稱常數(shù)級復(fù)雜度钓猬；數(shù)據(jù)規(guī)模變得有多大稍刀，花的時間也跟著變得有多長，這個程序的時間復(fù)雜度就是O(n)逗噩，比如找n個數(shù)中的最大值掉丽；而像冒泡排序、插入排序等异雁，數(shù)據(jù)擴大2倍捶障，時間變慢4倍的，屬于O(n^2)的復(fù)雜度纲刀。還有一些窮舉類的算法项炼，所需時間長度成幾何階數(shù)上漲，這就是O(a^n)的指數(shù)級復(fù)雜度示绊，甚至O(n!)的階乘級復(fù)雜度锭部。不會存在O(2*n^2)的復(fù)雜度，因為前面的那個“2”是系數(shù)面褐，根本不會影響到整個程序的時間增長拌禾。同樣地，O (n^3+n^2)的復(fù)雜度也就是O(n^3)的復(fù)雜度展哭。因此湃窍，我們會說，一個O(0.01*n^3)的程序的效率比O(100*n^2)的效率低匪傍，盡管在n很小的時候您市，前者優(yōu)于后者，但后者時間隨數(shù)據(jù)規(guī)模增長得慢役衡，最終O(n^3)的復(fù)雜度將遠遠超過O(n^2)茵休。我們也說，O(n^100)的復(fù)雜度小于O(1.01^n)的復(fù)雜度手蝎。
? ? 容易看出榕莺，前面的幾類復(fù)雜度被分為兩種級別，其中后者的復(fù)雜度無論如何都遠遠大于前者：一種是O(1),O(log(n)),O(n^a)等柑船，我們把它叫做多項式級的復(fù)雜度帽撑，因為它的規(guī)模n出現(xiàn)在底數(shù)的位置；另一種是O(a^n)和O(n!)型復(fù)雜度鞍时，它是非多項式級的亏拉，其復(fù)雜度計算機往往不能承受。當我們在解決一個問題時逆巍，我們選擇的算法通常都需要是多項式級的復(fù)雜度及塘，非多項式級的復(fù)雜度需要的時間太多，往往會超時锐极，除非是數(shù)據(jù)規(guī)模非常小笙僚。
? ? 自然地，人們會想到一個問題：會不會所有的問題都可以找到復(fù)雜度為多項式級的算法呢灵再？很遺憾肋层，答案是否定的亿笤。有些問題甚至根本不可能找到一個正確的算法來，這稱之為“不可解問題”(Undecidable Decision Problem)栋猖。The Halting Problem就是一個著名的不可解問題净薛，在我的Blog上有過專門的介紹和證明。再比如蒲拉，輸出從1到n這n個數(shù)的全排列肃拜。不管你用什么方法，你的復(fù)雜度都是階乘級雌团，因為你總得用階乘級的時間打印出結(jié)果來燃领。有人說，這樣的“問題”不是一個“正規(guī)”的問題锦援，正規(guī)的問題是讓程序解決一個問題猛蔽，輸出一個“YES”或“NO”（這被稱為判定性問題），或者一個什么什么的最優(yōu)值（這被稱為最優(yōu)化問題）雨涛。那么枢舶，根據(jù)這個定義，我也能舉出一個不大可能會有多項式級算法的問題來：Hamilton回路替久。問題是這樣的：給你一個圖凉泄，問你能否找到一條經(jīng)過每個頂點一次且恰好一次（不遺漏也不重復(fù)）最后又走回來的路（滿足這個條件的路徑叫做Hamilton回路）。這個問題現(xiàn)在還沒有找到多項式級的算法蚯根。事實上后众，這個問題就是我們后面要說的NPC問題。
? ? 下面引入P類問題的概念：如果一個問題可以找到一個能在多項式的時間里解決它的算法颅拦，那么這個問題就屬于P問題蒂誉。P是英文單詞多項式的第一個字母。哪些問題是P類問題呢距帅？通常NOI和NOIP不會出不屬于P類問題的題目右锨。我們常見到的一些信息奧賽的題目都是P問題。道理很簡單碌秸，一個用窮舉換來的非多項式級時間的超時程序不會涵蓋任何有價值的算法绍移。
? ? 接下來引入NP問題的概念。這個就有點難理解了讥电，或者說容易理解錯誤蹂窖。在這里強調(diào)（回到我竭力想澄清的誤區(qū)上），NP問題不是非P類問題恩敌。NP問題是指可以在多項式的時間里驗證一個解的問題瞬测。NP問題的另一個定義是，可以在多項式的時間里猜出一個解的問題。比方說月趟，我RP很好灯蝴，在程序中需要枚舉時，我可以一猜一個準⌒⒆冢現(xiàn)在某人拿到了一個求最短路徑的問題绽乔，問從起點到終點是否有一條小于100個單位長度的路線。它根據(jù)數(shù)據(jù)畫好了圖碳褒，但怎么也算不出來，于是來問我：你看怎么選條路走得最少看疗？我說沙峻，我RP很好，肯定能隨便給你指條很短的路出來两芳。然后我就胡亂畫了幾條線摔寨，說就這條吧。那人按我指的這條把權(quán)值加起來一看怖辆，嘿是复，神了，路徑長度98竖螃，比100小淑廊。于是答案出來了，存在比100小的路徑特咆。別人會問他這題怎么做出來的季惩，他就可以說，因為我找到了一個比100 小的解腻格。在這個題中画拾，找一個解很困難，但驗證一個解很容易菜职。驗證一個解只需要O(n)的時間復(fù)雜度青抛，也就是說我可以花O(n)的時間把我猜的路徑的長度加出來。那么酬核，只要我RP好蜜另，猜得準，我一定能在多項式的時間里解決這個問題愁茁。我猜到的方案總是最優(yōu)的蚕钦，不滿足題意的方案也不會來騙我去選它。這就是NP問題鹅很。當然有不是NP問題的問題嘶居，即你猜到了解但是沒用，因為你不能在多項式的時間里去驗證它。下面我要舉的例子是一個經(jīng)典的例子邮屁，它指出了一個目前還沒有辦法在多項式的時間里驗證一個解的問題整袁。很顯然，前面所說的Hamilton回路是NP問題佑吝，因為驗證一條路是否恰好經(jīng)過了每一個頂點非常容易坐昙。但我要把問題換成這樣：試問一個圖中是否不存在Hamilton回路。這樣問題就沒法在多項式的時間里進行驗證了芋忿，因為除非你試過所有的路炸客，否則你不敢斷定它“沒有Hamilton回路”。
? ? 之所以要定義NP問題戈钢，是因為通常只有NP問題才可能找到多項式的算法痹仙。我們不會指望一個連多項式地驗證一個解都不行的問題存在一個解決它的多項式級的算法。相信讀者很快明白殉了，信息學(xué)中的號稱最困難的問題——“NP問題”开仰，實際上是在探討NP問題與P類問題的關(guān)系。
? ? 很顯然薪铜，所有的P類問題都是NP問題众弓。也就是說，能多項式地解決一個問題隔箍，必然能多項式地驗證一個問題的解——既然正解都出來了谓娃，驗證任意給定的解也只需要比較一下就可以了。關(guān)鍵是蜒滩，人們想知道傻粘，是否所有的NP問題都是P類問題。我們可以再用集合的觀點來說明帮掉。如果把所有P類問題歸為一個集合P中弦悉，把所有 NP問題劃進另一個集合NP中，那么蟆炊，顯然有P屬于NP』颍現(xiàn)在，所有對NP問題的研究都集中在一個問題上涩搓，即究竟是否有P=NP污秆？通常所謂的“NP問題”，其實就一句話：證明或推翻P=NP昧甘。
? ? NP問題一直都是信息學(xué)的巔峰良拼。巔峰，意即很引人注目但難以解決充边。在信息學(xué)研究中庸推，這是一個耗費了很多時間和精力也沒有解決的終極問
題常侦，好比物理學(xué)中的大統(tǒng)一和數(shù)學(xué)中的歌德巴赫猜想等。
? ? 目前為止這個問題還“啃不動”贬媒。但是聋亡，一個總的趨勢、一個大方向是有的际乘。人們普遍認為坡倔，P=NP不成立，也就是說脖含，多數(shù)人相信罪塔，存在至少一個不可能有多項式級復(fù)雜度的算法的NP問題。人們?nèi)绱藞孕臥≠NP是有原因的养葵，就是在研究NP問題的過程中找出了一類非常特殊的NP問題叫做NP-完全問題垢袱，也即所謂的 NPC問題。C是英文單詞“完全”的第一個字母港柜。正是NPC問題的存在，使人們相信P≠NP咳榜。下文將花大量篇幅介紹NPC問題夏醉，你從中可以體會到NPC問題使P=NP變得多么不可思議。
? ? 為了說明NPC問題涌韩，我們先引入一個概念——約化(Reducibility畔柔，有的資料上叫“歸約”)。
? ? 簡單地說臣樱，一個問題A可以約化為問題B的含義即是靶擦，可以用問題B的解法解決問題A，或者說雇毫，問題A可以“變成”問題B玄捕。《算法導(dǎo)論》上舉了這么一個例子棚放。比如說枚粘，現(xiàn)在有兩個問題：求解一個一元一次方程和求解一個一元二次方程。那么我們說飘蚯，前者可以約化為后者馍迄，意即知道如何解一個一元二次方程那么一定能解出一元一次方程。我們可以寫出兩個程序分別對應(yīng)兩個問題局骤，那么我們能找到一個“規(guī)則”攀圈，按照這個規(guī)則把解一元一次方程程序的輸入數(shù)據(jù)變一下，用在解一元二次方程的程序上峦甩，兩個程序總能得到一樣的結(jié)果赘来。這個規(guī)則即是：兩個方程的對應(yīng)項系數(shù)不變，一元二次方程的二次項系數(shù)為0。按照這個規(guī)則把前一個問題轉(zhuǎn)換成后一個問題撕捍，兩個問題就等價了拿穴。同樣地，我們可以說忧风，Hamilton回路可以約化為TSP問題(Travelling Salesman Problem默色，旅行商問題)：在Hamilton回路問題中，兩點相連即這兩點距離為0狮腿，兩點不直接相連則令其距離為1腿宰，于是問題轉(zhuǎn)化為在TSP問題中，是否存在一條長為0的路徑缘厢。Hamilton回路存在當且僅當TSP問題中存在長為0的回路吃度。
? ? “問題A可約化為問題B”有一個重要的直觀意義：B的時間復(fù)雜度高于或者等于A的時間復(fù)雜度。也就是說贴硫，問題A不比問題B難椿每。這很容易理解。既然問題A能用問題B來解決英遭，倘若B的時間復(fù)雜度比A的時間復(fù)雜度還低了间护，那A的算法就可以改進為B的算法，兩者的時間復(fù)雜度還是相同挖诸。正如解一元二次方程比解一元一次方程難汁尺，因為解決前者的方法可以用來解決后者。
? ? 很顯然多律，約化具有一項重要的性質(zhì)：約化具有傳遞性痴突。如果問題A可約化為問題B，問題B可約化為問題C狼荞，則問題A一定可約化為問題C辽装。這個道理非常簡單，就不必闡述了相味。
? ? 現(xiàn)在再來說一下約化的標準概念就不難理解了：如果能找到這樣一個變化法則如迟，對任意一個程序A的輸入，都能按這個法則變換成程序B的輸入攻走，使兩程序的輸出相同殷勘，那么我們說，問題A可約化為問題B昔搂。
? ? 當然玲销，我們所說的“可約化”是指的可“多項式地”約化(Polynomial-time Reducible)，即變換輸入的方法是能在多項式的時間里完成的摘符。約化的過程只有用多項式的時間完成才有意義贤斜。
? ? 好了策吠，從約化的定義中我們看到，一個問題約化為另一個問題瘩绒，時間復(fù)雜度增加了猴抹，問題的應(yīng)用范圍也增大了。通過對某些問題的不斷約化锁荔，我們能夠不斷尋找復(fù)雜度更高蟀给，但應(yīng)用范圍更廣的算法來代替復(fù)雜度雖然低，但只能用于很小的一類問題的算法阳堕。再回想前面講的P和NP問題跋理，聯(lián)想起約化的傳遞性，自然地恬总，我們會想問前普，如果不斷地約化上去，不斷找到能“通吃”若干小NP問題的一個稍復(fù)雜的大NP問題壹堰，那么最后是否有可能找到一個時間復(fù)雜度最高拭卿，并且能“通吃”所有的 NP問題的這樣一個超級NP問題？答案居然是肯定的贱纠。也就是說峻厚，存在這樣一個NP問題，所有的NP問題都可以約化成它并巍。換句話說，只要解決了這個問題换途，那么所有的NP問題都解決了懊渡。這種問題的存在難以置信，并且更加不可思議的是军拟，這種問題不只一個剃执，它有很多個，它是一類問題懈息。這一類問題就是傳說中的NPC 問題肾档，也就是NP-完全問題。NPC問題的出現(xiàn)使整個NP問題的研究得到了飛躍式的發(fā)展辫继。我們有理由相信怒见，NPC問題是最復(fù)雜的問題。再次回到全文開頭姑宽，我們可以看到遣耍，人們想表達一個問題不存在多項式的高效算法時應(yīng)該說它“屬于NPC問題”。此時炮车，我的目的終于達到了舵变，我已經(jīng)把NP問題和NPC問題區(qū)別開了酣溃。到此為止，本文已經(jīng)寫了近5000字了纪隙，我佩服你還能看到這里來赊豌，同時也佩服一下自己能寫到這里來。
? ? NPC問題的定義非常簡單绵咱。同時滿足下面兩個條件的問題就是NPC問題碘饼。首先，它得是一個NP問題麸拄；然后派昧，所有的NP問題都可以約化到它。證明一個問題是 NPC問題也很簡單拢切。先證明它至少是一個NP問題蒂萎，再證明其中一個已知的NPC問題能約化到它（由約化的傳遞性，則NPC問題定義的第二條也得以滿足淮椰；至于第一個NPC問題是怎么來的五慈，下文將介紹），這樣就可以說它是NPC問題了主穗。
? ? 既然所有的NP問題都能約化成NPC問題泻拦，那么只要任意一個NPC問題找到了一個多項式的算法，那么所有的NP問題都能用這個算法解決了忽媒，NP也就等于P 了争拐。因此，給NPC找一個多項式算法太不可思議了晦雨。因此架曹，前文才說，“正是NPC問題的存在闹瞧，使人們相信P≠NP”绑雄。我們可以就此直觀地理解，NPC問題目前沒有多項式的有效算法奥邮，只能用指數(shù)級甚至階乘級復(fù)雜度的搜索万牺。
? ? 順便講一下NP-Hard問題。NP-Hard問題是這樣一種問題洽腺，它滿足NPC問題定義的第二條但不一定要滿足第一條（就是說脚粟，NP-Hard問題要比 NPC問題的范圍廣）。NP-Hard問題同樣難以找到多項式的算法蘸朋，但它不列入我們的研究范圍珊楼，因為它不一定是NP問題。即使NPC問題發(fā)現(xiàn)了多項式級的算法度液，NP-Hard問題有可能仍然無法得到多項式級的算法厕宗。事實上画舌，由于NP-Hard放寬了限定條件，它將有可能比所有的NPC問題的時間復(fù)雜度更高從而更難以解決已慢。
? ? 不要以為NPC問題是一紙空談曲聂。NPC問題是存在的。確實有這么一個非常具體的問題屬于NPC問題佑惠。下文即將介紹它朋腋。
? ? 下文即將介紹邏輯電路問題。這是第一個NPC問題膜楷。其它的NPC問題都是由這個問題約化而來的旭咽。因此，邏輯電路問題是NPC類問題的“鼻祖”赌厅。
? ? 邏輯電路問題是指的這樣一個問題：給定一個邏輯電路穷绵，問是否存在一種輸入使輸出為True。
? ? 什么叫做邏輯電路呢特愿？一個邏輯電路由若干個輸入仲墨，一個輸出，若干“邏輯門”和密密麻麻的線組成揍障∧垦看下面一例，不需要解釋你馬上就明白了毒嫡。
? ┌───┐
? │ 輸入1├─→┐? ? ┌──┐
? └───┘? ? └─→┤? ? │
? ? ? ? ? ? ? ? ? ? ? │ or ├→─┐
? ┌───┐? ? ┌─→┤? ? │? ? │? ? ┌──┐
? │ 輸入2├─→┤? ? └──┘? ? └─→┤? ? │
&
nbsp;└───┘? ? │? ? ? ? ? ? ? ? ┌─→┤AND ├──→輸出
? ? ? ? ? ? ? ? └────────┘┌→┤? ? │
? ┌───┐? ? ┌──┐? ? ? ? ? ? │? └──┘
? │ 輸入3├─→┤ NOT├─→────┘
? └───┘? ? └──┘
? ? 這是個較簡單的邏輯電路癌蚁，當輸入1、輸入2兜畸、輸入3分別為True努释、True、False或False膳叨、True洽洁、False時痘系，輸出為True菲嘴。
? ? 有輸出無論如何都不可能為True的邏輯電路嗎？有汰翠。下面就是一個簡單的例子龄坪。
? ┌───┐
? │輸入1 ├→─┐? ? ┌──┐
? └───┘? ? └─→┤? ? │
? ? ? ? ? ? ? ? ? ? ? │AND ├─→┐
? ? ? ? ? ? ? ? ┌─→┤? ? │? ? │
? ? ? ? ? ? ? ? │? ? └──┘? ? │? ┌──┐
? ? ? ? ? ? ? ? │? ? ? ? ? ? ? ? └→┤? ? │
? ┌───┐? ? │? ? ? ? ? ? ? ? ? ? │AND ├─→輸出
? │輸入2 ├→─┤? ┌──┐? ? ? ┌→┤? ? │
? └───┘? ? └→┤NOT ├→──┘? └──┘
? ? ? ? ? ? ? ? ? ? └──┘
? ? 上面這個邏輯電路中，無論輸入是什么复唤，輸出都是False健田。我們就說，這個邏輯電路不存在使輸出為True的一組輸入佛纫。
? ? 回到上文妓局，給定一個邏輯電路总放，問是否存在一種輸入使輸出為True，這即邏輯電路問題好爬。
? ? 邏輯電路問題屬于NPC問題局雄。這是有嚴格證明的。它顯然屬于NP問題存炮，并且可以直接證明所有的NP問題都可以約化到它（不要以為NP問題有無窮多個將給證明造成不可逾越的困難）炬搭。證明過程相當復(fù)雜，其大概意思是說任意一個NP問題的輸入和輸出都可以轉(zhuǎn)換成邏輯電路的輸入和輸出（想想計算機內(nèi)部也不過是一些 0和1的運算）穆桂，因此對于一個NP問題來說宫盔，問題轉(zhuǎn)化為了求出滿足結(jié)果為True的一個輸入（即一個可行解）。
? ? 有了第一個NPC問題后享完，一大堆NPC問題就出現(xiàn)了灼芭，因為再證明一個新的NPC問題只需要將一個已知的NPC問題約化到它就行了。后來驼侠，Hamilton 回路成了NPC問題姿鸿，TSP問題也成了NPC問題。現(xiàn)在被證明是NPC問題的有很多倒源，任何一個找到了多項式算法的話所有的NP問題都可以完美解決了苛预。因此說，正是因為NPC問題的存在笋熬，P=NP變得難以置信热某。P=NP問題還有許多有趣的東西，有待大家自己進一步的挖掘胳螟。攀登這個信息學(xué)的巔峰是我們這一代的終極目標∥舨觯現(xiàn)在我們需要做的，至少是不要把概念弄混淆了糖耸。
