np-complete

1熱度

3回答

我想嘗試尋找解決旅遊推銷員問題的啓發式/近似方法，爲了做到這一點，我正在尋找一些「硬」TSP實例（以及他們最知名的解決方案），以便我可以試着解決他們，看看我能做些什麼。理想情況下，它們只是一個基於文本的鄰接矩陣或鄰接表列表（我不想處理解析，只是算法）。「硬」，我的意思是他們應該幾乎不可能解決或近似使用暴力。（這是這樣，我可以有理由相信，如果我找到接近最佳已知答案的答案，那麼我實際上做正確的事

2熱度

1回答

NP類：爲什麼多項式長度輸出？

對於一個問題晉級NP類：該問題的解決方案必須具有多項式輸出的長度，以及該解決方案必須是在多項式時間內可覈查。多項式輸出長度的意義是什麼？ PS：我認爲多項式輸出長度是輸出在多項式時間內可驗證的必要前提條件。（但是隻是說可以用多項式時間驗證解決方案仍然足夠。）

5熱度

1回答

雙指數問題？

計算機科學中是否有任何重大問題只能在double exponential時間內解決？如果它們存在，那麼它們屬於哪類問題？

0熱度

1回答

我如何證明2-CNF不是NP-complete？

我想知道我可以證明2-CNF不是NP-hard或NP是否完整？任何人都可以在這方面幫助我。我迫切需要解決方案。

1熱度

1回答

從最大獨立集合減少到支配集合以證明支配集合是NP完全的

我知道從頂點覆蓋減少到支配集合。但是，我看到是否可以從最大獨立集問題直接減少到支配集問題，以證明後一個NP完全。有誰知道這是否已經完成？我無法在網上找到任何東西。我希望能找到像沿證明的東西線：如果有一個支配集大小爲k - >還有一個最大獨立集大小爲k。 AND 如果有一個最大獨立集大小爲k的 - >然後有一個控制集大小爲k。

0熱度

1回答

當NP完全變爲NP時

一般來說，假設我們有一個NPC問題。給它增加更多的約束（使它更難），這個問題有可能成爲NPH嗎？我知道NPC和NPH之間的區別，但我不知道如何證明給現有的NPC增加新的限制會使它成爲NPH還是仍然是NPC？

1熱度

1回答

NP很難但不是NPC

我已經看到幾個調度問題，說問題是NP難。我的問題是， 1）當我們說一個問題是NP很難，這是否意味着它不在NP？因爲如果它是NP，我們說這個問題是NP完全的。我知道一個問題是在NPC中，如果 a）它在NP b）NP難。

3熱度

2回答

以下哪種語言是NP完成的？

我在找NP和NP-complete問題的區別。我在Jason的StackOverflow中找到了這個偉大的答案。他說，關於NP完全問題，他說一個NP問題X可以在多項式時間內減少任何其他NP問題Y到X.直觀地說，這意味着如果我們知道如何快速求解X，我們可以快速求解Y.正確地說，如果存在多項式時間算法f，以便在多項式時間內將X的實例x變換爲Y的實例y = f（x），並且x的回答爲是的性質，當且僅當答

1熱度

1回答

Bin-packing解決方案：這是怎麼回事？

我試圖實施a bin-packing-type problem的解決方案，主要是以described by Dietrich Epp的方式。我沒有做Haskell，所以我用C++編寫了一些東西。對於低於特定數目（36）的牆寬，我的程序和Haskell程序給出了相同的結果。對於36個單位寬或更寬的牆，我的結果要低得多。我懷疑我的解決方案是否正確，因爲其他海報在這裏有很多「代表」。我相信問題在於我的

1熱度

3回答

數獨多項式算法？

我有一個項目要做複雜性和解決問題的課程，並且我決定將該項目建立在Sudoku上。從我所做的研究中，Sudoku是一個NP-Complete問題（這是項目需要的），並且我發現了幾種創建算法的方法。我打算做一個強力解決方法，我需要做另外兩種方法。我找到了一些方法，比如將它解決爲一個精確的封面問題，並且我找到了一篇將Sudoku描述爲SAT問題的論文。但我的問題是：Sudoku是否有一個經過驗證的多項式