NP完全性

探討各種各樣問題是否具有NP完全性，研究NP完全問題的處理方法，這對許多實際問題的演演算法設計和分析很有幫助，並與NP=?P等理論問題密切相關(見非確定性)。人們在這方面開展了大量研究工作，已逐漸形成一個專門性的理論──NP完全性理論。

巡迴銷售員問題也稱貨郎擔問題，是一個著名的NP完全問題。假定有一個銷售員要到 n個城鎮去推銷產品，已知各城鎮間的距離和一個界限B。問是否有一條旅行路線，恰好通過每個城鎮一次，最後回到出發點，且使旅行路線的總長不超過 B。巡迴銷售員問題實際是一類問題。當對城鎮數、城鎮間距離和界限 B給定具體數值后，就能得到其中一個具體問題，有時也稱作巡迴銷售員問題的一個“實例”。演演算法是針對巡迴銷售員這類問題而言的，即對其中任何實例都應是行之有效的。

P和NP對於一個問題，如果存在一個圖靈機，對這個問題的任何實例，都能給出回答，那麼這個問題就稱作可解的；如果存在一個圖靈機，又存在一介多項式P，在給定問題的實例后（設n是給定實例在0、1編碼下的長度)，這個圖靈機能在P(n)步內給出回答，那麼該問題稱作多項式時間可解的。

圖靈機可分為確定型和非確定型。確定型圖靈機在多項式時間內可解決的全部問題類記作 P。非確定型圖靈機在多項式時間內可解決的全部問題類，記作NP。由於確定型機器是非確定型機器的特殊情形，故P吇NP。有趣的是相反的問題:NP吇P?這就是著名的“NP=?P問題”。許多人猜測NP厵P,即在NP中有不是多項式時間可解的問題。在直覺上如果這種問題存在的話，它就是NP中“最難的”問題。NP完全問題就是NP中最難問題的一種形式化。

多項式時間歸約假定給了兩個問題類q和q0,如果存在一個確定型圖靈機Mq和一個多項式P,對於q中任意一個實例x,Mq都能在P(n)時間內計算出q0中一個實例y(其中n是實例x的編碼長度)，使得x是q中有肯定回答的實例，當且僅當y是q0中有肯定回答的實例，我們就說q多項式時間歸約到q0。

NP完全問題對於一個問題q0,如果q0屬於NP，且NP中任意一個問題，都能夠多項式時間歸約到q0，則稱q0為NP完全的，或q0具有NP完全性。除巡迴銷售員問題外，在實踐中還發現有大量的NP完全問題，它們來自計算機科學、數學、邏輯學等許多學科領域，總數已超過2000。下面是若干有代表性的NP完全問題。

①頂點覆蓋問題：給定一個圖G=(V，E),V為頂點集合,E為邊集合，又給定一個正整數K。問V是否有一個子集V′,其頂點數不超過K，並使G中每條邊都能被V′覆蓋，即每條邊的兩個頂點中至少有一個在V′中。

②三維匹配問題：三個班級，各有K人，共同參加某項活動。活動中，要求三人一組，組中每班一人。三人彼此認識的組稱為相識組。假定已知全部可能的相識組，問從中能否選出K個相識組，使得每人能參加且僅能參加一個相識組。

③分割問題：給定一堆自然數, 是否能將它們分成兩部分，使得這兩部分自然數各自的和彼此相等。

④帶優先次序的調度問題：有m個處理機和一個任務集合，每個任務的執行時間為1,已知任務間的優先次序（不一定每對任務間都有優先次序）和一個截止時間D。問是否有一個m個處理機的調度方法，滿足給定的優先次序，且在截止時間D以前結束全部任務。

⑤可滿足性問題：對任意給定布爾表達式，是否可對式中各變元賦予真值和假值，使該表達式的值為真。

可滿足性問題是歷史上第一個NP完全問題，它由S.A.庫克於1971年提出。

意義NP完全性的研究在理論上有重要意義。已經證明，只要有一個NP完全問題屬於P,則NP中一切問題都屬於P。實際上,NP中任何一個問題都可以多項式時間歸約到這個NP完全問題，而該問題又可在多項式時間內解決，故NP中任何問題都可在多項式時間內解決。因此，只要能證明任何一個NP完全問題屬於P,就能推出NP=P。這將導致十多年來計算機科學中一個重大問題──“NP=?P問題“的肯定性解決。反之，要否證NP=P，一個明顯的方法，就是到NP中去找一個不屬於P的問題。作為NP中“最難”問題的NP完全問題，自然是最有希望的候選對象。總之，無論是要證明還是要否證NP=P，NP完全問題的研究，都是很有意義的。

NP完全性的研究在實踐中有重要指導作用。在演演算法設計和分析過程中，如果已證明某問題是NP完全的，這就意味著面臨的是一個難於處理的問題。對於它，要找出一個在計算機上可行的（即多項式時間的）演演算法是十分困難的，甚至可能根本找不到(因為很可能有NP厵P)。因此，對於NP完全問題，最好是去尋找近似解法，或者針對該問題的某些有實用價值的特殊情況，尋找多項式時間演演算法。

M.R.Garey and D.S.Johnson, Computers and Intractability, A Guide to Theory of NP-Completeness,W.H.Freeman and Co.,San Francisco,1979.