np - 優文庫

np

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難。

0熱度

1回答

什麼是第一個被稱爲NP Complete的算法？

應該有一個最初的問題開始建立一套NPC問題。只有這樣才能將問題添加到集合NPC中，從集合NP中顯示出NP中的問題可以簡化爲NPC中的第一個問題。那麼，什麼是第一個被添加到NPC的問題，以及某個人是如何得出結論的，那就是確實是NPC。（注：谷歌搜索，沒有回答，我希望這裏有人的教授曾提到在課堂上是這樣的。）

3熱度

2回答

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

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

0熱度

1回答

NP完全減少

我對於與NP完全問題有關的減少有這個困惑。假設我們有兩個問題R和S不知道在NP中。現在如果我們有一個衆所周知的NP完全問題的多項式時間減少到R，並且我們也有一個從S到NP完全問題的多項式時間減少。對於R和S問題可以說什麼呢？它們是NP完成的還是NP很難？

0熱度

2回答

是否可以證明NP-Complete概率不存在多項式算法？

我真的無法真正瞭解它是什麼意思，說一個問題是NP完成。任何人都可以幫我解決以下問題嗎？一個NP完全問題是一個問題，人們可以證明一個算法在多項式時間求解它不存在。這個陳述是真實的嗎？我想說這種說法是不正確的，因爲任何人實際上證明這種算法不存在任何NP完全問題？從各種來源四處觀看，我知道對於任何NP完全問題，沒有多項式時間算法是已知的;但是，它不能被證明。任何幫助將不勝感激。謝謝。

2熱度

1回答

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

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

3熱度

2回答

TSP NP-Hard如何？

我讀SO : 旅行商問題的答案之一以下，因爲通常所構成的，是找到連接所有城市的最便宜的路線。這不是一個決策問題，我們無法直接驗證任何提議的解決方案。我們可以將其重述爲一個決策問題：給定成本C，是否存在比C更便宜的路線？這個問題是NP完全的，通過一些工作，我們可以像修改的NP完全形式一樣容易地解決原始TSP。因此，TSP是NP難的，因爲它至少與NP完全問題一樣困難。我知道TSP是NP-Comple

5熱度

1回答

雙指數問題？

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

0熱度

1回答

工作調度問題的變化

我正在爲航空運輸公司做一些管理工作。他們在這裏建造飛機容器等。他們希望我編寫代碼的一件事就是一個訂單優化腳本，這些腳本可以讓場內人員充分利用所提供的材料。爲了給出一個簡單的概述：假設我們訂購一定數量的單位爲10米的光束。我們需要5x6m，10x3.5m，4x3m的波束塊，這些波塊通過在較小的部分切割10m而獲得。我們需要訂購的最小數量爲10m的光束是多少？有一些相似之處上述多任務調度問題（一個束