np - 優文庫

np

0熱度

2回答

我是一名計算機科學專業的學生，我在理解基於驗證者的NP問題定義時遇到了一些問題。的定義說，一個問題是NP如果能夠在polinomial時間確定性圖靈機，給出了「證書」驗證。但會發生什麼，如果證書正是問題的解決方案？這只是一點點，它在輸入規模上顯然受到多項式限制，並且顯然可以在恆定的，因此是多項式時間中進行驗證。因此，每個決策問題都屬於NP。我在哪裏錯了？

2熱度

1回答

0-1揹包是否每個項目具有相同的權重NP-complete？

0-1揹包問題被稱爲NP-complete。但是如果每件商品的重量都相同，問題仍然是NP完全的？

3熱度

4回答

所有的NP問題都是NP完成的嗎？

的NP-完整的定義是的問題是NP完全如果它屬於類NP 所有NP的其他問題多項式的變換，那麼，如果NP中的所有其他問題轉化爲NP完全問題，那麼這是否也意味着所有NP問題都是NP完全問題呢？如果兩者相同，對它們進行分類有什麼意義？換句話說，如果我們有一個NP問題，那麼通過（2）這個問題可以轉化爲一個NP完全問題。因此，NP問題現在是NP完全的，NP = NP完全。兩個類都是等價的。只是試圖

12熱度

3回答

單元測試近似算法

我正在使用一些流行的python軟件包作爲基礎，開發圖形和網絡的開源逼近算法庫。主要目標是包含圖形和網絡上NP-Complete問題的最新近似算法。原因是1）我還沒有看到一個很好的（現代）整合包，它涵蓋了這個，2）它將是一個很好的學習NP-Hard優化問題的近似算法的教學工具。在構建這個庫時，我使用單元測試來進行健全性檢查（就像任何適當的開發人員一樣）。我對自己的單元測試有點謹慎，因爲從本質上來

7熱度

2回答

最大獨立集算法

我不相信存在於比尋找所有可能的獨立集合中最大的蠻力方法以外的二分圖中發現的最大獨立頂點集的算法。我想知道關於僞代碼來找到所有可能的頂點集。說給出4個藍色頂點和4紅色二分圖。目前，我會 Start with an arbitrary blue, find all red that don't match this blue put all these red in Indep

2熱度

1回答

是有限因子共NP？

有限因子。給定數n，決定它是否有任何適當的因子小於k。這是一個合作Np的問題？

0熱度

1回答

是否有可能寫一個程序以打印從添加大小爲n

的輸入陣列到k是否有可能寫一個程序以打印從添加大小n的輸入陣列到k的所有對所有對。如果是這樣如何？我聽說這個問題是NP-Complete。我想知道，我們可以在像典型的編程語言提供了一個解決這個問題的C/C++

12熱度

1回答

證明暫停問題是NP-hard？

（對於這個問題，如果這是錯誤的網站，我很抱歉，但考慮到有很多「CS不夠理想」CS理論問題在這裏浮動，我認爲這可能是一個很好的選擇請隨意移動這個，如果它是不恰當的。）在this answer到約NP，NP難的定義問題，NP完全，傑森使得聲稱停機問題是經典的NP難題。這是給定程序P和輸入I的問題，它會停止嗎？這是一個決策問題，但它不在NP中。很明顯，任何NP完全問題都可以歸結爲這個問題。儘管我認

0熱度

1回答

減少到np硬

Wiki說，當你將poly時間的np complte問題轉換爲A時，A很難。看到http://en.wikipedia.org/wiki/NP-hard 但下面的PDF說，當你在多項式時間內轉換爲NP難問題問題A，A是NP - 難 http://compgeom.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/21-nphard.pdf 哪一個，我應該相

1熱度

1回答

是否有任何知名的NP完全問題，我可以減少「節點佈局」問題？

我有以下NP完全問題：給定一組N個N字段中的一組位置，以及一組m個節點，還有一個節點的連通圖（即一個無向圖，其邊緣代表每對與每個節點接觸的節點）以及接觸範圍R（與N×N字段具有相同的長度單位），在關於連接圖的字段中找到節點的位置（即放置節點，接觸的任何對接近比R和eny對不接觸比R更遠），或者表明這種放置不存在。我們是否有任何知名的NP完全問題，這個問題可以簡化爲？（也可以考慮優化版本的問題