Math：P問題(多項(xiàng)式時間內(nèi)可解決)、NP問題(多項(xiàng)式時間內(nèi)驗(yàn)證)、NPC問題(可通過一個多項(xiàng)式時間算法轉(zhuǎn)換為NP問題)、NP-Hard問題(兩不知)的詳解與區(qū)別之詳細(xì)攻略
導(dǎo)讀：昨天與圈內(nèi)幾位數(shù)學(xué)界的大佬，深度探討了一下P問題、NP問題、NPC問題、NP-Hard問題之間的聯(lián)系和區(qū)別，聊的很嗨，主要是來比較復(fù)雜問題的困難程度，探究是否存在高效算法解決NP問題的可能性，并為復(fù)雜問題提供高效近似算法。進(jìn)一步，幫助我們理解問題的可解性和難解性。
研究P問題和NP問題可以幫助我們了解在可接受的時間內(nèi)是否存在高效算法來解決某個問題。而NPC問題和NP-Hard問題的研究則對于確定問題的邊界和復(fù)雜性提供了重要線索。這些理論概念在算法設(shè)計(jì)、計(jì)算復(fù)雜性理論以及實(shí)際問題的解決中具有廣泛的應(yīng)用。
歡大家留言評論，參與探討與分享……
目錄
P問題(多項(xiàng)式時間內(nèi)可解決)、NP問題(多項(xiàng)式時間內(nèi)驗(yàn)證)、NPC問題(可通過一個多項(xiàng)式時間算法轉(zhuǎn)換為NP問題)、NP-Hard問題(兩不知)的詳解與區(qū)別
P問題(多項(xiàng)式時間內(nèi)可解決)、NP問題(多項(xiàng)式時間內(nèi)驗(yàn)證)、NPC問題(可通過一個多項(xiàng)式時間算法轉(zhuǎn)換為NP問題)、NP-Hard問題(兩不知)的詳解與區(qū)別
| 問題復(fù)雜度 |
多項(xiàng)式級的復(fù)雜度：一種是O(1)，O(log(n))，O(na)等，我們把它叫做多項(xiàng)式級的復(fù)雜度，因?yàn)樗囊?guī)模n出現(xiàn)在底數(shù)的位置； 非多項(xiàng)式級復(fù)雜度：另一種是O(an)和O(n!)型復(fù)雜度，它是非多項(xiàng)式級的，其復(fù)雜度計(jì)算機(jī)往往不能承受。 |
|
| 當(dāng)我們在解決一個問題時，我們選擇的算法通常都需要是多項(xiàng)式級的復(fù)雜度，非多項(xiàng)式級的復(fù)雜度需要的時間太多，往往會超時，除非是數(shù)據(jù)規(guī)模非常小。 |
||
| UDP問題 |
會不會所有的問題都可以找到復(fù)雜度為多項(xiàng)式級的算法呢？很遺憾，答案是否定的。有些問題甚至根本不可能找到一個正確的算法來，這稱之為“不可解問題” (Undecidable Decision Problem)。 |
|
| P類問題 |
P類問題：P代表可在多項(xiàng)式時間內(nèi)解決的問題。這些問題的解決方案可以在多項(xiàng)式時間內(nèi)找到。也就是說，存在一個有效的算法，其運(yùn)行時間與問題的規(guī)模呈多項(xiàng)式關(guān)系。 所有可以在多項(xiàng)式時間內(nèi)求解的判定問題構(gòu)成P類問題。其中判定問題：判斷是否有一種能夠解決某一類問題的能行算法的研究課題。 如果一個問題可以找到一個能在多項(xiàng)式的時間里解決它的算法，那么這個問題就屬于P問題(Polynomial)。 哪些問題是P類問題呢？通常NOI和NOIP不會出不屬于P類問題的題目。我們常見到的一些信息奧賽的題目都是P問題。道理很簡單，一個用窮舉換來的非多項(xiàng)式級時間的超時程序不會涵蓋任何有價(jià)值的算法。 |
例如，排序和搜索算法都屬于P問題； 奧賽的題目都是P問題； |
| NP類問題 |
NP類問題(Non-deterministic Polynomial)：NP代表非確定性多項(xiàng)式（Nondeterministic Polynomial）。這類問題的解決方案可以在多項(xiàng)式時間內(nèi)驗(yàn)證，但是找出解決方案的時間復(fù)雜度可能是指數(shù)級的。 。也就是說，如果我們已經(jīng)有了一個解決方案，我們可以在多項(xiàng)式時間內(nèi)驗(yàn)證它的正確性。然而，尚未找到多項(xiàng)式時間復(fù)雜度的解決方案。經(jīng)典的例子是旅行商問題（Traveling Salesman Problem），即找到一條訪問所有城市的最短路徑。 所有的非確定性多項(xiàng)式時間可解的判定問題構(gòu)成NP類問題。其中非確定性算法將問題分解成猜測和驗(yàn)證兩個階段。算法的猜測階段是非確定性的，算法的驗(yàn)證階段是確定性的，它驗(yàn)證猜測階段給出解的正確性。 NP問題容易理解錯誤。在這里強(qiáng)調(diào)，NP問題不是非P類問題。NP問題是指 >> 可以在多項(xiàng)式的時間里驗(yàn)證一個解的問題。 >> 可以在多項(xiàng)式的時間里猜出一個解的問題。 找一個解很困難，但驗(yàn)證一個解很容易。驗(yàn)證一個解只需要O(n)的時間復(fù)雜度，也就是說我可以花O(n)的時間把我猜的路徑的長度加出來。 |
例如旅行商問題、求解線性方程組。 |
| NP=P？可能是這個世紀(jì)最重要的數(shù)學(xué)問題 |
||
| NPC問題 |
NPC問題(Non-deterministic Polynomial Complete)：如果任何一個NP問題都能通過一個多項(xiàng)式時間算法轉(zhuǎn)換為某個NP問題，那么這個NP問題就稱為NPC問題。 NPC代表非確定性多項(xiàng)式完全（Nondeterministic Polynomial Complete）。這是一類特殊的NP問題，被認(rèn)為是NP問題中最難的問題之一。如果某個問題是NPC問題，那么它滿足兩個條件： 首先，它是一個NP問題； 其次，任何其他的NP問題都可以通過多項(xiàng)式時間歸約（reduction）轉(zhuǎn)換為該問題。 簡而言之，NPC問題是NP問題的最困難的子集。著名的例子包括旅行商問題、背包問題（Knapsack Problem）和布爾可滿足性問題（Boolean Satisfiability Problem）。 NP中的某些問題的復(fù)雜性與整個類的復(fù)雜性相關(guān)聯(lián)，這些問題中任何一個如果存在多項(xiàng)式時間的算法，那么所有NP問題都是多項(xiàng)式時間可解的，這些問題被稱為NP-完全問題(NPC問題)。 |
著名的例子包括0-1背包問題、布爾可滿足性問題 |
| NP-Hard |
NP-Hard問題是一類至少與NPC問題一樣困難的問題。它們可以是任何問題，即使沒有被證明為NP問題。NP-Hard問題不一定要求在多項(xiàng)式時間內(nèi)驗(yàn)證解決方案，也沒有要求它們本身是NP問題。簡單來說，NP-Hard問題是困難問題的一類，并且可以用多項(xiàng)式時間歸約轉(zhuǎn)換為任何其他問題。 兩不知：這類問題目前不知道是否可以在多項(xiàng)式時間內(nèi)解決，也不知道解的驗(yàn)證是否可以在多項(xiàng)式時間內(nèi)完成。文章來源：http://www.zghlxwxcb.cn/news/detail-612089.html |
圖的著色問題文章來源地址http://www.zghlxwxcb.cn/news/detail-612089.html |
到了這里，關(guān)于Math：P問題(多項(xiàng)式時間內(nèi)可解決)、NP問題(多項(xiàng)式時間內(nèi)驗(yàn)證)、NPC問題(可通過一個多項(xiàng)式時間算法轉(zhuǎn)換為NP問題)、NP-Hard問題(兩不知)的詳解與區(qū)別之詳細(xì)攻略的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
