NP困難
（重新導向自NP-hard）
頁面Module:Message box/mbox.css沒有內容。
此條目需要擴充。 (2013年3月12日) |
package.lua第80行Lua錯誤：module 'Module:CGroup/core' not found
頁面Module:Hatnote/styles.css沒有內容。
NP困難（NP-hardness, non-deterministic polynomial-time hardness）問題是計算複雜性理論中最重要的複雜性類之一。如果所有NP問題都可以多項式時間歸約到某個問題，則稱該問題為NP困難。
因為NP困難問題未必可以在多項式時間內驗證一個解的正確性（即不一定是NP問題），因此即使NP完全問題有多項式時間的解（P=NP），NP困難問題依然可能沒有多項式時間的解。因此NP困難問題「至少與NP完全問題一樣難」。
參見[編輯]
參考文獻[編輯]
- package.lua第80行Lua錯誤：module 'Module:Citation/CS1/People' not found
- Hollinger G, Singh S. Multi-robot coordination with periodic connectivity[C]//Robotics and Automation (ICRA), 2010 IEEE International Conference on. IEEE, 2010: 4457-4462.
- Singh A, Krause A, Guestrin C, et al. Efficient informative sensing using multiple robots[J]. Journal of Artificial Intelligence Research, 2009, 34: 707-755.
package.lua第80行Lua錯誤：module 'Module:Navbar/configuration' not found