NP困難

术语

NP困難NP-hardness, non-deterministic polynomial-time hardness)問題是計算複雜性理論中最重要的複雜性類別之一。如果所有NP問題都可以多項式時間歸約到某個問題,則稱該問題為NP困難。

描述P, NP, NP完全,以及NP困難之間關係的歐拉圖

因為NP困難問題未必可以在多項式時間內驗證一個解的正確性(即不一定是NP問題),因此即使NP完全問題有多項式時間的解(P=NP),NP困難問題依然可能沒有多項式時間的解。因此NP困難問題「至少與NP完全問題一樣難」。

參見

參考文獻

  • Michael R. Garey; David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. 1979. ISBN 0-7167-1045-5. 
  • 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.