![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完備 (NP-Complete,縮寫為NP-C或NPC),是計算複雜度理論中,決定性問題的等級之一。NP完備是NP與NP困難問題的交集,是NP中最難的決定性問題,所有NP問題都可以在多項式時間內被歸約(reduce to)為NP完全問題。倘若任何NP完全問題得到多項式時間內的解法,則該解法就可應用在所有NP問題上,亦可證明NP問題等於P問題,然而目前為止並未發現任何能在多項式時間內解決NP完全問題的方法。
![]() | 此條目需要精通或熟悉計算機科學的編者參與及協助編輯。 (2012年10月14日) |
![]() | 此條目內容疑欠準確,有待查證。 (2012年10月14日) |
![](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)