np-complete

0熱度

2回答

我想知道如何需要許多比特來編碼的布爾公式像 @(x1,x2,x3,x4) = (x1 OR x2 OR NOT(x3) OR x4) AND ((NOT)x2 OR x3) AND (x1 OR (NOT)x4) @是SAT的一個實例。我認爲它是4位，因爲可能的組合總數是2（power4）。那是對的嗎？我應該計算OR，NOT，還是計算編碼所需的位數？我搜查了很多，但無法找到任何東西。

3熱度

1回答

最小頂點覆蓋的驗證算法？

我們知道最小頂點覆蓋是NP完整的，這意味着它是可以在多項式時間內驗證的一組問題。據我所知，驗證過程需要下列：驗證解決方案是一個頂點覆蓋在所有驗證解決方案是源圖的最小可能的子集滿足條件＃1 我很難確定第2步可以在多項式時間內完成。任何人都可以解釋它是如何？

0熱度

1回答

PartitionProblem - 找到最優的子集

我需要找到最優的子集，解決分區問題後，使用動態規劃僞多項式時間算法。更具體地說，我不能讓這個答案的意義：https://stackoverflow.com/a/890243/1317826 我無法理解如何從布爾表構建最佳的子集。分區上的問題維基百科的文章有太：http://en.wikipedia.org/wiki/Partition_problem 是否有人可以擺脫一些關於它的光？

3熱度

1回答

NP-complete的複雜度測量

例如，集合覆蓋決策問題已知是一個NP完全問題。這個問題的輸入是宇宙U，U的子集S和一個整數k（）。我很困惑的一件事是，如果讓k = 1，那麼通過簡單地檢查S中的每個元素，顯然問題可以在時間| S |中解決。更一般地，當k是常數，問題可以用| S |的多項式時間來解決。在這樣的方式，時間複雜度成倍成爲僅高當k也增加| S |像| S |/2，| S |/3 ...... 所以我這裏還有我的問題：

-4熱度

1回答

如何演示NP-complete

如何證明下一個問題是NP-complete。給定一個矩陣A和b一個向量，找到一個滿足不等式Ax≤b的非負整數向量x。

1熱度

2回答

一些NP-Complete問題又如何成爲NP-Hard？

我試圖以直觀的方式包裝我聽到的P，NP，NP-Complete和NP-Hard，這樣我就不必記住他們的定義。在下圖（左手腳，P！= NP）中，NP-Complete和NP-Hard之間有一個重疊區域。這是否意味着某些問題既是NP-Complete又是NP-Hard？我發現這個矛盾，根據這個特殊的答案：What are the differences between NP, NP-Complete

0熱度

2回答

Numberlink/Flow Game：如何識別NP-Complete問題？

我試圖找到一種方法來解決着名的遊戲流程中的問題。 http://moh97.us/flow/ 谷歌搜索後，我發現這是一個NP完全問題。一個好的解決方案會利用啓發式和削減。我如何輕鬆發現NP完全問題？有時當我阻止時，我看不到明顯的解決方案。當這種情況發生在NP-complete上時，最好快速識別它並轉到下一個問題。

0熱度

1回答

旅行商TSP：蠻力算法改進

根據wiki將需要（N-1）！計算與N個城市的遊覽。我發現了一個更好的方法來做到這一點，但我無法用數學來計算我改進了多少。我可以告訴你，在我的家用電腦上，我能夠在不到1個小時內解決20個城市的地圖。 20！ = 2.43290200e + 18。這是我做的：當使用brout算法搜索N個城市的路線時（讓我們給他們一個名字：City（1），City（2），City（3）... City（N））（1

2熱度

2回答

這是證明某件事情是否完整的正確理解？

據我所知有兩個步驟來證明一個問題是NP完全性：給出了一種算法，可以驗證在多項式時間內解決問題。也就是說，一種算法，其輸入是提出的問題解決方案，其輸出是「是」還是「否」，取決於輸入是否是問題的有效解決方案。證明這個問題是NP難 - 比如，假設你有一個可以在一個步驟計算其它已知的NP完全問題的神諭。使用它，編寫一個在多項式時間內解決這個問題的算法。例如，假設我們要證明下面的問題是NP完全性：給

3熱度

2回答

NP完全 - 可以在非確定性多項式時間中求解

它寫在一本書中 - 「如果問題A是NP-完全的，則存在用於求解A的非確定性多項式時間算法。但據我所知'是' - 對於NP完整問題可以在多項式時間內「驗證」。我很困惑。使用非確定性多項式時間算法可以解決NP完全問題嗎？