![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/a/a0/P_np_np-complete_np-hard.svg/langzh-hk-640px-P_np_np-complete_np-hard.svg.png&w=640&q=50)
NP困難
术语 / 維基百科,自由的 encyclopedia
NP困難(NP-hardness, non-deterministic polynomial-time hardness)問題是計算複雜性理論中最重要的複雜性類別之一。如果所有NP問題都可以多項式時間歸約到某個問題,則稱該問題為NP困難。
此條目需要擴充。 (2013年3月12日) |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a0/P_np_np-complete_np-hard.svg/640px-P_np_np-complete_np-hard.svg.png)
因為NP困難問題未必可以在多項式時間內驗證一個解的正確性(即不一定是NP問題),因此即使NP完全問題有多項式時間的解(P=NP),NP困難問題依然可能沒有多項式時間的解。因此NP困難問題「至少與NP完全問題一樣難」。