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日) |