np-complete

5熱度

3回答

考慮以下問題：有編號爲1到N 你不能看到他們ň硬幣，但鑑於有關它們的形式的M個事實： struct Fact { set<int> positions int num_heads } positions識別硬幣的一個子集，並且num_heads是該子集中硬幣的頭數。鑑於這些M事實，您需要計算出可能的最大頭數。這個問題NP-complete？如果是，那麼減少是多少？

0熱度

1回答

減少到np硬

Wiki說，當你將poly時間的np complte問題轉換爲A時，A很難。看到http://en.wikipedia.org/wiki/NP-hard 但下面的PDF說，當你在多項式時間內轉換爲NP難問題問題A，A是NP - 難 http://compgeom.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/21-nphard.pdf 哪一個，我應該相

0熱度

2回答

是否可以證明NP-Complete概率不存在多項式算法？

我真的無法真正瞭解它是什麼意思，說一個問題是NP完成。任何人都可以幫我解決以下問題嗎？一個NP完全問題是一個問題，人們可以證明一個算法在多項式時間求解它不存在。這個陳述是真實的嗎？我想說這種說法是不正確的，因爲任何人實際上證明這種算法不存在任何NP完全問題？從各種來源四處觀看，我知道對於任何NP完全問題，沒有多項式時間算法是已知的;但是，它不能被證明。任何幫助將不勝感激。謝謝。

4熱度

2回答

比較語法樹模α-轉化

我工作的編譯器/防爆檢查，我想知道，如果我有一個語法樹像這樣的，例如：如果有辦法檢查Expr的alpha等價（等價模更名）。然而，這個Expr與lambda演算的不同之處在於，λ中的變量集是可交換的 - 即參數的順序不涉及檢查。（爲簡單起見，Lambda ["x","y"] ...不同於Lambda ["x"] (Lambda ["y"] ...)，在這種情況下，順序很重要）。換句話說

0熱度

1回答

基於節點和邊權重的圖分區

我有一個圖G =（V，E），這兩個邊和節點都有權重。我想分割這個圖來創建相同大小的分區。分區大小的定義是sum（vi）-sum（ej）其中vi是該分區內的節點，ej是該分區中兩個節點之間的邊緣。在我的問題中，圖很密集（幾乎完成）。有什麼近似算法嗎？這在某種程度上類似於bin packing with overlapping objects中垃圾箱尺寸相同的問題。節點的重量是它們的大小和重量的邊緣

1熱度

1回答

證明數值問題的NP完備性時的數基的作用

我正在讀tardos算法設計手冊中有關NP完備性的內容，在證明子集和的部分是NP完整的，它寫成 - 該算法開發用於子集總和的運行時間爲O（nW）。如果給出100個數字的實例，其中每一個都是100位長，那麼輸入僅爲100 * 100 = 10000位，但W大約爲2^100。我不明白這個說法，爲什麼是W 2^100？基於這個問題的效果是什麼，我的意思是如果我們將它改爲其他基礎x，W是x^100？如果

5熱度

1回答

將驗證算法轉換爲SAT問題的編譯器

SAT是NP完全的證明是一種建設性證明，所以應該可以將其作爲程序來實現。有沒有人做過這個？我正在尋找一個程序（一個編譯器），它將一個程序（它返回true或false）作爲輸入並輸出一個SAT公式。例如，編譯器可以將以下程序（以pythonic語法顯示，但任何語言都適合我）作爲輸入，並輸出SAT公式。將SAT公式提供給SAT求解器將給出參數「證書」的解決方案。在這種情況下，解決方案會是[假，真，真

2熱度

1回答

0-1揹包是否每個項目具有相同的權重NP-complete？

0-1揹包問題被稱爲NP-complete。但是如果每件商品的重量都相同，問題仍然是NP完全的？

11熱度

6回答

建議算法（圖 - 可能是NP-Complete）

有一個城鎮網絡，由各種整數長度的道路相連。一位旅行者希望在他的車上從一個小鎮旅行到另一個小鎮。但是，他不想盡量減少行駛距離，相反，他希望儘量減少旅程的汽油成本。汽油可以在任何城市購買，但每個城市以各種（整數）價格供應汽油（因此爲什麼最短路線不一定是最便宜的）。 1個汽油單位使他能駕駛1個單位的距離。他的汽車只能在汽油箱中裝載如此多的汽油，他可以選擇在每個城市旅行時購買多少汽油。找到最低汽油成本

3熱度

2回答

資源約束的最短路徑

我有一個有向無環圖，需要找到資源約束的最短路徑。我的約束是所選路徑必須具有消耗的最小數量的設置資源。目前我使用Yen's K Shortest Path algorithm計算K最短路徑，然後只接受那些滿足我的約束。這裏的問題在於猜測K，就好像它被錯誤地選擇一樣，可能沒有找到可行的路徑。我發現很多這方面的文獻，this提供了一個很好的概述，我認爲。然而，我很難理解它，並找到一個能夠實現的簡潔算