np-complete

4熱度

2回答

爲什麼不是這兩個問題，即TSP和Hamiltonian path problem，都是NP-complete？它們看起來完全相同。

0熱度

1回答

這是我在堆棧溢出中找到的答案」NP是一個複雜類，它表示所有決策問題的集合，其答案爲「是」的實例具有可在多項式時間內驗證的證明。這意味着如果有人給我們提供了一個問題的實例和一個證書（有時稱爲見證），答案是肯定的，我們可以檢查它在多項式時間內是否正確。「 -jason 我的問題是誰是「我們」，檢查在多項式時間solution是否正確？這是一個程序，還是它真的意味着一個人坐下來在紙上工作？這可能是

0熱度

1回答

NP完整的定義

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

3熱度

1回答

約束揹包不重

我只是碰到下面的問題就來了（這讓我想起揹包-問題的，但是也有一些區別）：現在給你的項目數量爲n的，你必須把裏面的你具有最大利潤的揹包。每個項目都有一個特定的利潤值和一個特定的形狀。由於它們的形狀，一些物品不能一起放入揹包。與普通揹包問題不同，沒有最大重量限制揹包中物品的數量。您還會得到每個項目的清單。在該列表中，您可以看到可以放入揹包中的物品以及相應的物品。是否有一種算法可以計算出最優解？

0熱度

1回答

減法如何通過矛盾來證明硬度？

我不是一個參加計算複雜課程的學生，只是對這個主題感興趣。我遇到這個部分：假設我們有一個問題，我們已經證明很難解決，和我們有一個類似的新問題。我們可能會懷疑它也是難以解決的。我們通過矛盾來辯論：假設新問題容易解決，就是。那麼，如果我們能夠證明舊問題的每個實例都可以通過將其轉化爲新問題的實例並解決這些問題而輕易解決，那麼我們就會產生矛盾。這確定新問題也很難。來源：Wikipedia 我似乎

0熱度

1回答

最小支配集軟件

交叉發佈這個from CS Theory因爲它更像是一個軟件問題。我需要一個代碼來計算確切的MIN-DOM-SET。目前建議的最佳選擇是將其制定爲SMT問題並將其投入SMT解決方案。好奇的是，如果有任何良好的MIN-DOM-SET特定代碼或良好的SMT-LIB制定。

0熱度

1回答

將三着色降爲10着色（NP-完整性）

我試圖證明3-着色圖的NP完全問題降低爲10-着色圖的問題。我已經展示了10 - 色彩可以用多項式時間來驗證，因此在NP中。現在我只需要證明它確實可以減少爲三色。我的想法本質上證明了一個雙向條件：給定一個圖G，我們知道G有一個3着色，如果G有一個10着色。現在，我不知道該如何去展示，因爲很顯然，G可以有10種顏色而不是3種顏色。所以這讓我相信，在某種程度上必定會有一些減少G的變化，讓我看到，是的

1熱度

2回答

子集大小爲'k`的子集合是NPC嗎？

我有一個Subset-Sum problem的變化，其中子集的大小是k，並且所有整數都是正數（而非零）。從網上可以看出，這個問題可以用僞多項式時間的動態規劃來解決。我需要決定這個問題是NPC，還是在P（同時假設P!=NP）。我試圖減少子集和問題，但有一個約束，所有整數必須大於零的問題。除此之外，我會用k填充零輸入。問題的正式定義： L={<S1,S2,...,Sn,T,k>|There e

0熱度

1回答

找到給定黑盒子的相等分區，如果在考試準備期間存在一個

，則返回true，但我發現這個問題，我無法解決，也無法在網上找到解決方案。我一直在掙扎幾個小時試圖找出這一個沒有運氣。問題消失如下：給出一個黑盒子，如果存在子集2Ť和S/T一套小號具有相等的總和和假如果沒有，則返回true，在多項式時間。假設你給了一個集合S，並且上面的黑盒子找到了一個子集T，其中T和和（S/T）的和是相等的。在此先感謝。

1熱度

1回答

NP-complete問題也是NP-hard嗎？

我們可以說，一個NP完全問題是一個NP和NP難的問題，但我們能否僅僅因爲它是NP完全的事實而認爲問題是NP-hard。示例：我將一個NP完成問題a減少爲問題b。因此，問題b現在被證明是NP完全的。我真的可以說這也是NP難嗎？