np - VoidCC

np

1熱度

1回答

我想使用圖3的着色性來證明問題是NP完全的但我不確定何時給定的圖是3着色的。我想如果它沒有任何節點連接到圖中三角形的所有3個頂點，但我不確定。這是對的嗎？

1熱度

1回答

我讀了這本書計算機和難解性 - NP完整性理論指南 Garey和Johnson爲我的算法課程;然而，一年後，在回顧這些材料時，我意識到我從來沒有真正理解庫克定理。關於這個證明，我理解爲什麼SAT首先被證明是NP（NP-complete的第一個要求），但是我正在努力通過證明在其他NP問題下的「其他」NP完全問題「遺傳」多項式轉換爲SAT。我在想，如果有人能在一個更淡化的方式解釋，這或許會澄清這部

2熱度

1回答

改性pisinger

到subsetsum算法我被pisinger看算法這裏詳述 Fast solution to Subset sum algorithm by Pisinger ，並在維基百科上http://en.wikipedia.org/wiki/Subset_sum_problem For the case that each xi is positive and bounded by a fixed con

0熱度

1回答

這個蠻力算法NP-hard？

下面是我們在項目管理系統中使用的一種蠻力算法，用於從摘要中提取關鍵字。那個蠻力算法的時間複雜度是多少？在NP中還是在P中，是NP-NP還是NP-complete？這是算法： public static int search(String pattern, String text) { int M = pattern.length(); int N = text.length(

1熱度

1回答

每種語言都屬於P還是NP？

爲什麼我正在閱讀關於Michael Sipser計算理論的書，我有一個小問題：每種語言是屬於P還是NP？

1熱度

1回答

MAX 3 SAT NP-complete或co-NP-complete？

我看到有關此問題的許多衝突信息。有些網站說它是NP完整的，而另一些網站則說它是NP-complete。我能找到的唯一真正一致的信息是絕對是NP難。這是什麼？爲什麼？

1熱度

1回答

類布爾到布爾可滿足性[多項式時間減少]第2部分

我問幾天前，一個關於如何將大學課堂排序問題轉換爲布爾可滿足性問題的問題。（Class Scheduling to Boolean satisfiability [Polynomial-time reduction]）我通過@Amit回答誰是非常優雅，易於代碼。基本上，他的答案是這樣的：他不考慮課程，而是考慮時間間隔。因此，對於第i個課程，他只是指出了本課程的所有可能的時間間隔。當每個課程至

-2熱度

1回答

如果P！= NP，P是否比非P問題多，反之亦然？

如果P！= NP，那麼比SuperPolynomial問題還有更多的多項式問題，反之亦然？

0熱度

2回答

Bin包裝的變化 - 與箱和對象類和相互約束

我正在研究一個問題，這是一個變形的bin-packing，但有一個更多的一般形式與額外的約束。問題定義如下 - 我們有不同大小的對象，可以將它們組合到對象類中。我們有不同容量的容器，它們也被分爲容器類（同一類容器中的所有容器都具有相同容量）。對象類對它們可以放置在哪些容器上具有約束 - 例如，可以將類「A」的對象放置在容器類「X」或「Y」中的任一個中。其目標是找到每個班級的垃圾桶的最小數量，這可以

1熱度

2回答

實用最大化作業

我發佈了這個計算機科學部分，但沒有人回覆:(任何幫助將不勝感激:)。有一個大小爲MxN的網格。 M〜20000和N〜10。所以M非常大。因此，一種方法是看看這是N個並排放置的大小爲M的網格塊。接下來假設有K個用戶，每個用戶都有一個MxN的實用程序矩陣，其中每個元素提供用戶在該用戶被分配該網格元素時將獲得的實用程序。分配需要按照每個分配用戶的方式完成，在每個網格塊中，總效用必須超過特定的閾值效用U