回答啊4兄的問題。

很顯然，不是說我找不到Polynomial的算法，那這個問題就是NP，那只能證明我笨。

標(biāo)準(zhǔn)辦法是從一個已知的NP問題推導(dǎo)出這個問題，而這個推導(dǎo)的復(fù)雜程度是Polynomial的。

這可以用反證法來證明：

已知問題A是NP問題，而且經(jīng)過一番推導(dǎo)可以得出問題B，而這個推導(dǎo)是Polynomial的。假設(shè)問題B是P，即存在Polynomial(O(n^c))算法可以解決問題B，那么我們就可以先把問題A轉(zhuǎn)化為問題B，再解決問題B。因為這兩個步驟都是Polynomial的，也就是說我們發(fā)現(xiàn)了Polynomial的算法解決問題A。而這與已知問題A是NP問題矛盾。所以我們的假定是錯的，問題B一定也是NP問題。

我們看到了，所有的NP問題好像一條鐵鏈，一環(huán)套一環(huán)。如果我們對其中一個問題找到了Polynomial的算法，就砍斷了這條鐵鏈，解決了所有問題。

但這就牽扯到“第一個”的NP問題的問題。即：我們需要一個已知的NP問題來證明這個問題，那么很顯然，第一個NP問題不能用這個方法來證明。第一個NP問題是什么？它是怎么證明的？

對這個問題我沒有具體的研究過。我猜第一個NP問題是SAT問題，我知道有人用了一個NP的圖靈機解決了這個問題。學(xué)計算機的朋友們應(yīng)該知道，圖靈機是現(xiàn)代計算機的基本模型。

最后順便說一句，NP是Nondeterministic Polynomial的簡寫，標(biāo)準(zhǔn)翻譯應(yīng)該是“非決定性多項式”，而不是“非多項式”。