p=np是數學問題嗎

是。

p=np是數學問題嗎1

事實上，現代加密技術依賴於這樣一個事實：大質數不可能因式分解。這些問題似乎都有一個共同的難題，也就是P（ polynomial time）對NP（ non-deterministic polynomial time）謎題的核心——什麼是可化簡的，什麼是不可化簡的？

1859年，愛爾蘭數學家威廉·漢密爾頓畫了一個叫做伊科希的數學遊戲。這個遊戲是在一個由20個角（頂點）組成的木製十二面體表面上進行的。每個角落都標上了一個城市的名字。

遊戲的目標是找到一個循環，即訪問每個頂點一次，然後返回起點。這種路徑稱爲哈密頓循環。這個簡單的博弈產生了圖論中的一個重要問題，即哈密頓循環決策問題——給定一個任意地圖，我們如何知道它是否包含一個哈密頓循環？

二維平面圖形的十二面體。一個可能的哈密頓循環用紅色表示。

給出一個圖，確定它是否包含一個哈密頓循環。

解決這個問題的一種方法是遍歷圖中任何可能的路徑，並檢查該路徑是否爲哈密頓循環。然而，由於可能路徑的數量可以達到n的階乘。

　　

這樣，即使一個只有40個頂點的圖也可能包含超過10^45條路徑，使得問題幾乎不可能在合理的時間內解決(即使對於最強大的處理器也是如此)。

此外，由於頂點數量與路徑數量之間的階乘依賴關係，即使我們再增加一個頂點，也需要大幅提升計算機的'計算能力。我們可以說，階乘增長的根本性質使這個問題比其他問題更困難。

這就是數學問題的艱鉅性——如果一個問題需要的資源隨着投入的增加而急劇增加，那麼這個問題就非常棘手。

爲了使這個想法形式化，計算機科學家使用了時間複雜度的尺度。時間複雜度指的是解決一個問題需要多少步長，以及所需的步長如何隨問題的大小而變化。給定一個算法，算法的時間複雜度被描述爲一個漸近函數，它依賴於算法的輸入大小。

漸進觀點是計算複雜性理論所固有的，它揭示了有限而精確的分析所掩蓋的結構——阿維·威格森

一個算法的時間複雜度被描述爲一個漸近函數，它依賴於算法的輸入大小。一個主要的區別是階乘，指數和多項式複雜度函數。

對於具有多項式複雜度的算法和具有更基本複雜度函數的算法，有一個基本的區別。這種區別主要是由於多項式增長被認爲比其他增長更爲緩慢，因爲增大輸入不會導致所需步驟急劇增加。

多項式（Polynom）是一種只涉及加、減、乘和非負整數指數運算的構造，因此不是指數或階乘增長。選擇多項式來表示有效的計算似乎是任意的，然而，隨着時間的推移，它從許多角度證明了自己的合理性。

例如，多項式在加法、乘法和組合下的閉包保留了自然編程實踐中的效率概念，比如將程序鏈接到一個序列中，或者將一個程序嵌套到另一個程序中

p=np是數學問題嗎2

具有多項式時間複雜度的算法被稱爲“高效”。

多年來，爲了有效地解決哈密頓循環決策問題，科學家們進行了許多嘗試。其中一種是Held-Karp算法，它能在指數時間內解決這個問題。然而，沒有已知的算法可以在多項式時間內解決這個問題，因此，它仍然被認爲是一個難題。

邁克爾·赫爾德，理查德·史克和理查德·卡普。

然而，一個有趣的現象發生了，儘管我們不能有效地解決這個問題，給定一個路徑圖中，我們至少可以有效地檢查是否是哈密頓循環，因爲簡單循環中的最大頂點數爲n，則遍歷路徑所需的時間被多項式限定爲n。。

這種現象也出現在其他難題中，例如數獨決策問題——給定一個不完整的數獨網格，我們希望知道它是否至少有一個有效的解決方案。

任何提出的數獨解決方案都可以很容易地驗證，並且隨着網格的增大，檢查一個解決方案的時間會多項式的增長。然而，所有已知的尋找解決方案的算法，對於困難的例子，時間會隨着網格的增大呈指數增長。

與哈密頓路徑決策問題相似，目前還沒有任何已知的算法可以有效地解決數獨問題，但是，只要給出一個解，就可以有效地驗證該解。

似乎許多其他決策問題都具有這一特性——不管它們是否能被有效地解決，它們所提出的解決方案都能被有效地驗證。這類問題被定義爲NP。

　　

如果一個決策問題的解能被有效地驗證，那麼這個決策問題就是NP問題。

首字母縮寫NP代表不確定性多項式時間（儘管人們普遍認爲NP的意思是“非P”）。

進一步思考問題的可解性與其解的可驗證性之間的關係，我們可以得出下一個結論：如果一個決策問題是有效可解得，那麼它的解必須是有效可驗證的。

爲什麼？因爲如果一個決策問題是可以有效地解決的，那就意味着我們可以有效地找到它的解決方案。

然後，給出一個解決方案，我們可以簡單地通過與問題的實際解決方案比較來驗證它。換句話說，生成解決方案的算法的正確性自動證明了該解決方案。

從這個結論可以看出，很明顯，NP包含的問題子集也是有效可解的。這個子集被定義爲P。

P是所有可有效解決的`決策問題的集合，是NP的一個子集。基本算法是多項式時間可解的。象棋決策問題不屬於NP問題，因爲沒有一種有效的算法可以檢查給定的棋盤是否有效。魔方決策問題屬於NP問題，因爲判斷一個給定的魔方是否是一個解是很簡單的。

哈密頓路徑決策問題有一個有效的算法可以驗證它的解，因此，它屬於NP。有人可能會問這個問題是否在P中，一方面，我們不知道有一個有效的算法可以解決這個問題。

另一方面，沒有證據表明這樣的算法不存在。事實上，這樣的算法仍然有可能存在，而且還沒有被發現。數獨的決策問題也是一樣。

事實上，對於許多其他主要問題，包括布爾可滿足性問題，旅行推銷員問題，子集和問題，派系問題，圖着色問題——儘管我們已經證明這些問題是NP，但沒有證據表明他們在P 。這就是P=NP問題的意義所在：

p=np是數學問題嗎3

P和NP真的是一樣的嗎？

如果是的話，這就意味着NP中的所有問題都可以被有效地解決，儘管我們仍然沒有找到實現這一點的神祕算法。否則，在NP中存在一些無法有效解決的問題，任何嘗試解決將意味着浪費我們的時間和精力。

大多數時候，不能有效地解決問題是一件消極的事情。然而，在某些情況下，我們可以從問題的“硬度”中獲益。屬於NP而不屬於P的問題，其主要特點是很難解決，但很容易驗證其解決方案。

給定兩個正整數n和k，判斷n是否有一個質因數小於k。——質因數分解決策問題

由於該問題的解可以有效地驗證，因此我們知道該問題屬於NP，給定一個整數c，它需要“多項式時間”來知道c是否是一個比k小的質數，還是n的因數。

但是，目前還沒有一種算法可以在多項式時間內解決這一問題。因此，使用兩個相當大的質數，就可以計算它們的乘法，這用於生成一個公鑰和一個私鑰。

公鑰可以爲所有人所知，並用於加密消息。使用公鑰加密的消息只能在合理的時間內使用私鑰解密，假設沒有有效的方法將一個大整數分解爲它的質數因子。

　　

RSA-2048有617位十進制數字(2048位)。它是RSA數字中最大的，因式分解獲得的現金獎金最高，爲20萬美元。除非在不久的將來在整數因子分解或計算能力方面取得重大進展，否則RSA-2048在許多年內可能無法分解。

但是，如果P=NP，則最後一個假設是錯誤的。爲什麼？如果P等於NP，那麼質因數分解問題在P中，這意味着它可以被有效地解決。

因此，一旦找到這樣一個算法，任何公鑰都可以在合理的時間內解密，而不需要私鑰，這使得整個RSA密碼系統完全崩潰，至少在理論上如此。

但是P=NP的負面影響與它所具有的潛在好處相比，是無關緊要的.。在數學、優化、人工智能、生物學、物理學、經濟學和工業領域中，確實存在着數以千計的NP問題，這些問題都是出於不同的需要而自然產生的，而有效的解決方案將使我們在許多方面受益。

證明P=NP將意味着所有這些難題都可以在多項式時間內解決，這將導致在那些卓越的算法之後進行大規模的智力追求。一旦發現，這些算法將有可能推動人類的進步，遠遠超出我們的掌握。