P類問題的概念：如果一個問題可以找到一個能在多項式的時間里解決它的算法魂莫，那么這個問題就屬于P問題搅轿。

NP問題是指可以在多項式的時間里驗證一個解的問題贮泞。NP問題的另一個定義是，可以在多項式的時間里猜出一個解的問題旺嬉。

之所以要定義NP問題，是因為通常只有NP問題才可能找到多項式的算法厨埋。我們不會指望一個連多項式地驗證一個解都不行的問題存在一個解決它的多項式級的算法鹰服。所有的P類問題都是NP問題。也就是說揽咕，能多項式地解決一個問題悲酷，必然能多項式地驗證一個問題的解。

顯然有P屬于NP∏咨疲現(xiàn)在设易，所有對NP問題的研究都集中在一個問題上，即究竟是否有P=NP蛹头？通常所謂的“NP問題”枕赵，NP問題一直都是信息學(xué)的巔峰，其實就一句話：證明或推翻P=NP撇眯。

目前為止這個問題還“啃不動”县遣。但是，一個總的趨勢耕拷、一個大方向是有的讼昆。人們普遍認為，P=NP不成立骚烧，也就是說浸赫，多數(shù)人相信，存在至少一個不可能有多項式級復(fù)雜度的算法的NP問題赃绊。人們?nèi)绱藞孕臥≠NP是有原因的既峡，就是在研究NP問題的過程中找出了一類非常特殊的NP問題叫做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回路存在當(dāng)且僅當(dāng)TSP問題中存在長為0的回路。

“問題A可約化為問題B”有一個重要的直觀意義：B的時間復(fù)雜度高于或者等于A的時間復(fù)雜度旨涝。也就是說蹬屹，問題A不比問題B難。這很容易理解颊糜。既然問題A能用問題B來解決哩治，倘若B的時間復(fù)雜度比A的時間復(fù)雜度還低了，那A的算法就可以改進為B的算法衬鱼，兩者的時間復(fù)雜度還是相同。正如解一元二次方程比解一元一次方程難憔杨，因為解決前者的方法可以用來解決后者鸟赫。

約化具有傳遞性。如果能找到這樣一個變化法則，對任意一個程序A的輸入抛蚤，都能按這個法則變換成程序B的輸入台谢，使兩程序的輸出相同，那么我們說岁经，問題A可約化為問題B朋沮。當(dāng)然，我們所說的“可約化”是指的可“多項式地”約化(Polynomial-time Reducible)缀壤，即變換輸入的方法是能在多項式的時間里完成的樊拓。約化的過程只有用多項式的時間完成才有意義。

如果不斷地約化上去塘慕，不斷找到能“通吃”若干小NP問題的一個稍復(fù)雜的大NP問題筋夏，那么最后是否有可能找到一個時間復(fù)雜度最高，并且能“通吃”所有的 NP問題的這樣一個超級NP問題图呢？答案居然是肯定的条篷。也就是說，存在這樣一個NP問題蛤织，所有的NP問題都可以約化成它赴叹。換句話說，只要解決了這個問題指蚜，那么所有的NP問題都解決了稚瘾。這種問題的存在難以置信，并且更加不可思議的是姚炕，這種問題不只一個摊欠，它有很多個，它是一類問題柱宦。這一類問題就是傳說中的NPC 問題些椒，也就是NP-完全問題：首先，它得是一個NP問題掸刊；然后免糕，所有的NP問題都可以約化到它。??既然所有的NP問題都能約化成NPC問題忧侧，那么只要任意一個NPC問題找到了一個多項式的算法石窑，那么所有的NP問題都能用這個算法解決了，NP也就等于P 了蚓炬。因此松逊，給NPC找一個多項式算法太不可思議了。因此肯夏，前文才說经宏，“正是NPC問題的存在犀暑，使人們相信P≠NP”。我們可以就此直觀地理解烁兰，NPC問題目前沒有多項式的有效算法耐亏，只能用指數(shù)級甚至階乘級復(fù)雜度的搜索。

NP-Hard問題：它滿足NPC問題定義的第二條但不一定要滿足第一條（就是說沪斟，NP-Hard問題要比 NPC問題的范圍廣）广辰。NP-Hard問題同樣難以找到多項式的算法，但它不列入我們的研究范圍主之，因為它不一定是NP問題择吊。即使NPC問題發(fā)現(xiàn)了多項式級的算法，NP-Hard問題有可能仍然無法得到多項式級的算法杀餐。事實上干发，由于NP-Hard放寬了限定條件，它將有可能比所有的NPC問題的時間復(fù)雜度更高從而更難以解決史翘。

有了第一個NPC問題后枉长，一大堆NPC問題就出現(xiàn)了，因為再證明一個新的NPC問題只需要將一個已知的NPC問題約化到它就行了琼讽。后來必峰，Hamilton 回路成了NPC問題，TSP問題也成了NPC問題∽甑牛現(xiàn)在被證明是NPC問題的有很多吼蚁，任何一個找到了多項式算法的話所有的NP問題都可以完美解決了。因此說问欠，正是因為NPC問題的存在肝匆，P=NP變得難以置信。P=NP問題還有許多有趣的東西顺献，有待大家自己進一步的挖掘旗国。攀登這個信息學(xué)的巔峰是我們這一代的終極目標(biāo)。現(xiàn)在我們需要做的注整，至少是不要把概念弄混淆了能曾。

參考原文：https://blog.csdn.net/qq_39521554/article/details/79109278

常見時間復(fù)雜度：（數(shù)據(jù)結(jié)構(gòu)與算法）