是否存在某種方法能夠證明某個np問題能轉換為p問題？

01-29

個人理解：np問題是使用非確定性演算法在多項式時間內求解的問題，非確定性演算法又不是切實可行的演算法，我個人認為就是無法使用確定的演算法解決問題。
假設某個問題是np問題，能夠使用的方法都無法解決該問題，但是方法有無數種，不能證明所有的方法都用完了，那是不是就沒法證明所有的np問題都能轉換為p問題？

我一點一點慢慢答，先留個幾個要點。如果我對問題的理解有偏差，麻煩題主在評論里告知。

1. 需要區別〝非確定性演算法〞和 NTM

NTM是同時計算出所有可能出現的結果，注意，是同時。所以只要有一條計算路徑可以在多項式時間內跑完，就可以說這個問題屬於NP。

====分割線內的這段可以不看……===========================

而〝非確定性演算法〞可能不是並行的，比如ppt演算法 (probabilistic polynomial time algorithm)，這類演算法，如果你把它想像成自動機，則在運行時，每一跳會有一個隨機選項。但ppt單次運行最後形成的計算路徑是唯一的。這樣，就沒有了「同時計算出」這個性質。對於ppt最後計算出正確結果的總運行時間複雜度能求出一個期望值，而這個期望值可能並非是多項式的。但這個複雜度不代表問題不屬於NP。

===============================================================

2. NP 不等於NP- Complete (NP完全)

不是所有的NP問題都難。因為 $Psubseteq NP$ .

比如，求無負環的圖中兩點最短路徑的問題，或者驗證一個字元串是否是迴文的問題，都屬於P，因此也屬於NP，但都不是NP-Complete。

3.NP是否等於P還是個開放問題。

所有的P問題都是NP問題，這個結論從兩者的定義出發即可得。但反過來，即NP問題是否都是P問題，目前為止無法斷言。

在這個前提下，除了直接從定義出發，只能從證明特定的問題之間的等價關係開始，找尋這個問題的性質。比如SAT是個NP-complete問題，而clique問題和它等價，所以clique也是 NP-complete。要證明某個問題是否是p也類似，找到一個和它等價的、已知的p問題( 或者找到一個直接解決它的多項式複雜度演算法。)

4。目前為止， NP-complete僅僅是一個複雜度假設，一個便於研究問題性質的概念。因為就如你所說，或許僅僅是因為我們都還不夠聰明，所以找不到高效的演算法。

============2014年12月13日更新===========================

以下區別一下NP-hard 和 NP-Complete

1. 若任何一個NP問題都能夠在多項式時間內規約到問題A，則稱A為NP-hard問題。

2. 若A本身屬於NP，且滿足1，則稱A為NP-complete。

區別在於，可能存在本身不屬於NP，但是是NP-hard的問題。這類問題並非NP-Complete。

理論上就不行。因為只有兩種情況：

１.　這個問題只是NP，那麼只是證明了這個問題是NP的這個論點是錯誤的。那麼這個問題就被重新歸類為P問題。

２.　這個問題是NP-complete，　那麼就證明了NP=P。

PS：如果題主找到的是第二種，那五百萬美金分我個十分之一怎麼樣！！^。^