p-np

-1熱度

1回答

我參加了複雜性和問題解決方面的400級課程。最後的項目是實施一個與P和NP相關的問題。不幸的是，老師對項目的界限不明確。所以我只是想我會問在這裏看看是否有人對我可能實施的中度困難問題提出建議。我知道這個問題很模糊，但我很想聽聽有沒有人最喜歡的問題。謝謝！

23熱度

6回答

非NP完全困難的NP難題更難？

根據我的理解，所有NP完全問題都是NP難題，但是一些NP難題已知不是NP完全問題，而NP難問題至少和NP完全問題一樣困難。這是不是NP NP完全困難的NP難題？而且它更難嗎？

0熱度

1回答

NP完整的定義

我試圖理解NP Complete的正式定義並且有一些問題。我想知道如果有人能提供更多的見解。 Jon Kleinberg algorithms book表示如果每個NP問題都可以歸結爲問題X，那麼問題X在NP集合中。現在既然P是NP的一個子集，那麼我們可以將P中的任何問題都簡化爲多項式時間的NP完全問題。這導致一個矛盾，即由於減少是在多項式時間內，我們可以在多項式時間內解決這個NP完全問題。這不

2熱度

2回答

什麼是NP問題？

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

9熱度

8回答

P！= NP證明缺少什麼？

我試圖恢復密碼。在想到這一點時，我認識到「密碼恢復」這個問題是NP問題的一個很好的例子。如果您知道密碼，可以很容易地在多項式時間內進行驗證。但是如果您不知道密碼，您必須搜索可能會出現指數時間的可能解決方案的整個空間。現在我的問題是：這是否證明P！= NP，因爲「密碼恢復」是NP的一個元素，可以顯示需要超過多項式時間才能運行？

0熱度

1回答

3SAT求解多項式時間？

我已經看到了CNF文件，一些錯誤的兩種可滿足和不可滿足的條款文件SATLIB Benchmark Problems 更具體的我已經發現，Zip文件夾這裏的第一個文件： 20 variables, 91 clauses - 1000 instances, all satisfiable 包含的標題的文件（51917）和（-5-19）的「uf20-01」，它的方程式是清晰的，因爲第15行的第7個句子和

8熱度

1回答

P = NP：最有前途的方法是什麼？

我知道P = NP至今還沒有解決，但任何人都可以告訴我以下幾點：什麼是目前最有前途的數學/計算機科學方法，可以幫助解決這個問題？還是有沒有人知道迄今爲止這種方法可能有幫助？有沒有關於這個主題的任何（免費）概要，我可以找到在這方面所做的所有研究/大部分研究？