-
NP-Complete
(計算複雜性中的NP完全)
鎖定
- 中文名
- NP完全、NP完備
- 外文名
- NP-Complete
- 縮 寫
- NP-C 、NPC
釋義
一個決定性問題C若是為NPC,則代表它對NP是完備的,這表示:
- 它是一個NP問題,且
- 其他屬於NP的問題都可歸約成它。
可歸約在此意指對每個問題L,總有一個多項式時間多對一變換,即一個決定性的算法可以將實例l∈L轉化成實例c∈C,並讓c回答Yes當且僅當此答案對l也是Yes。為了證明某個NP問題A實際上是NPC問題,證明者必須找出一個已知的NPC問題可以變換成A。
本定義得到一個結論,就是若上述的C有一個多項式時間可解的算法,則我們可以將所有的NP問題降到P之中。
這個定義是史提芬·古克所提出。雖然NPC這個詞並沒有出現在這篇論文上任何地方。在這個資訊科學會議上,資訊科學家激動地討論NPC問題是否可以在一個確定型圖靈機上以多項式時間求解。John Hopcroft總結與會眾人的共識,認為由於沒有人能對某一命題提出駁倒對方的證明,此問題不會於現在解決。此命題就是知名的
- P和NP相等嗎?。
尚未有人能提出證明,説明NPC問題是否能在多項式時間中解決,使得此問題成為著名的數學中未解決的問題。 位於劍橋市的“克雷數學研究所”(Clay Mathematics Institute,簡稱CMI)提供了一百萬美金獎金給任何可以證明P=NP或P≠NP的人。
在1972年,Richard Karp證明有好幾個問題也是NPC(請見卡普的二十一個NP-完全問題),因此除了SAT問題外,的確存在着一整類NPC問題。從古克開始,數千個問題藉由從其他NPC問題變換而證實也是NPC問題,其中很多問題被蒐集在Garey與Johnson於1979年出版的書之中。
- 詞條統計
-
- 瀏覽次數:次
- 編輯次數:10次歷史版本
- 最近更新: 君伟junwei521