什麼是NP問題？

我讀了維基百科上的文章，但不明白NP問題到底是什麼。任何人都可以告訴我他們，還有他們與P問題的關係是什麼？什麼是NP問題？

2010-08-17 Shubham

一些提示這裏http://stackoverflow.com/questions/210829/what-is-an-np-complete-problem – c4il 2010-08-17 10:04:03

可能重複[什麼是「P = NP？」，爲什麼它是這樣一個着名的問題？]（http://stackoverflow.com/questions/111307/whats-pnp-and-why-is-it-such-a-famous-question） – Potatoswatter 2010-08-17 10:08:34

只需點擊右側的「p-np」標籤，即可提供許多問答很好地涵蓋了這個問題。 – Potatoswatter 2010-08-17 10:09:40

NP問題是指給定解決方案的問題，您可以在多項式時間內驗證解決方案。例如，如果您有大學課程列表並需要創建時間表以便課程不會發生衝突，那麼這將是一項非常困難的任務（複雜性）。但是，給出一個建議的時間表，您可以輕鬆驗證其正確性。

加密領域的另一個重要例子：給定一個數字，它是兩個非常大的素數相乘的結果，很難僅根據結果找到這些素數。但是，給出了兩個數字，很容易檢查解決方案（將它們相乘，比較）。

我有意選擇了NP中的例子，而不是P中的例子（即難以找到解決方案的問題），因此您可以瞭解其差異。所有易於解決的問題也很容易驗證 - 只需解決和比較即可。也就是說，P是NP的一個子集。

來源

2010-08-17 10:04:41

值得注意的是，儘管人們經常舉出難以計算的例子，但這不是定義的一部分（只是該地區有趣問題的一部分）。例如，整數加法是一個NP問題，因爲可以在多項式時間內*驗證答案。在這種情況下，計算也很簡單，這並不重要。 – 2010-08-17 10:09:47

不是一個真正的答案，因爲Piccolo的鏈接更有用，但惠普研究人員聲稱已經證明P！= NP，這裏是論文。

www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp12pt.pdf

它尚未被接受，但我希望他爲100萬$的好運氣。

來源

2010-08-17 10:09:58

我相信這個證據中的錯誤已經找到:) – 2010-08-17 10:11:25

什麼是NP問題？

回答

相關問題