np-complete

1熱度

1回答

如果P不等於NP可以證明沒有近似算法進入最佳頂點覆蓋的k，其中k是一個固定的常數？

0熱度

1回答

我讀過多個答案，發現有向圖中的所有循環都是NP完全的，但約翰遜的算法在圖中找到所有簡單循環，運行在O（（V + E）（C + 1））時間（其中C是圖中強連通分量的數目），我認爲這是多項式，因爲E < = V^2和C變成O（V^3）的V，對嗎？約翰遜的算法：http://www.cs.tufts.edu/comp/150GA/homeworks/hw1/Johnson%2075.PDF

2熱度

1回答

生成所有字符串排列NP完成？

通過嘗試所有可能性，可以在O（n！）中計算給定字符串的所有字符串置換。現在，看看旅行商問題，我們可以通過嘗試所有城市排列來解決它。假設我們有城市A，B和C. 假設我們從城市A開始。通過計算BC字符串的所有排列，我們得到ABC ACB，然後我們只求和（在多項式時間內，AB，CB和CA之間的距離爲第一種情況...）因此，這不是所有字符串排列的旅行商問題的減少，並不是一個NP完整的問題？

2熱度

1回答

NP完整嗎？

決策問題：對於給定的圖G和數字「a」，「b」，需要回答是否存在具有至少'b'大小的累積鄰域的一組'a'頂點。我們如何證明這個問題是NPC？

0熱度

1回答

超圖的頂點着色，不均勻性限制NP-hard？

是一個超圖的頂點着色，沒有統一性限制NP-hard？我看過顯示k-聯合超圖的頂點着色的論文是NP-hard。然而，我找不到任何明確說明在一般情況下（而不僅僅是k均勻）超圖的頂點着色是否是NP難的來源。

1熱度

1回答

顏色編碼算法的最長路徑

之前我想說清楚的是它是一個大學作業，我正在尋求幫助理解算法，以便能夠實現它。所以我這項任務的是凸輪在這裏找到： https://www.labri.fr/perso/dorbec/AA/projet-uno.pdf 基本上，我們有一組由2 INT一個代表的「卡」，表示卡的顏色，另一個用於數。要完成的工作是查找最長的卡片序列，例如UNO遊戲中下一張卡片的顏色或顏色相同或編號相同。因爲在詛咒中已經

1熱度

2回答

提出多項式算法

給定n個檢查，每個任意（整數）貨幣值，決定檢查是否可以分成具有相同貨幣值的兩個部分。我非常想到如何解決這個問題。有沒有一種算法可以在多項式時間內解決這個問題，還是NP-Complete？

0熱度

2回答

如果Y在多項式時間內可以歸約爲X，那麼X至少和Y一樣硬呢？

我很難理解兩類問題的複雜性之間的關係，比如NP-hard和NP-complete問題。答案在https://stackoverflow.com/a/1857342/狀態：直觀地說，這些都是至少一樣努力的NP完全問題的問題。請注意，NP-hard問題不必在NP和中，它們不必是決策問題。這裏的確切定義是：問題X是NP難的，如果有一個NP完全問題Y，這樣Y還原爲X在多項式時間。如果問題Y可以在多

5熱度

1回答

算法在處理器上調度作業

根據iehrlich的評論（感謝btw），術語「調度」可能是誤導，這可能是一個更合適的描述：給定一個矩陣N * N，找到一個行排列，將產生最大的對角線總和。我有一組N個就業機會和N處理器。所有處理器可以彼此不同。對於每個（作業，處理器）對，我都具有在該處理器上運行該作業的性能。性能是在IPC（指令每週期）中測量的。我試圖發現最大化IPC的整體和時間表（1對1的分配）。我可以通過檢查所有可能的時

0熱度

1回答

0,1揹包減少子集總和

我知道如何將子集和減少到0,1揹包。但是是否有可能將揹包減少到子集總和？怎麼樣？