[拼音]：NP wanquanxing

[外文]：NP-completeness

計(jì)算復(fù)雜性理論中的一個(gè)重要概念，它表征某些問題的固有復(fù)雜度。一旦確定一類問題具有NP完全性時(shí)，就可知道這類問題實(shí)際上是具有相當(dāng)復(fù)雜程度的困難問題。

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

巡回銷售員問題

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

P和NP

對(duì)于一個(gè)問題，如果存在一個(gè)圖靈機(jī)，對(duì)這個(gè)問題的任何實(shí)例，都能給出回答，那么這個(gè)問題就稱作可解的；如果存在一個(gè)圖靈機(jī)，又存在一介多項(xiàng)式P，在給定問題的實(shí)例后（設(shè)n是給定實(shí)例在0、1編碼下的長(zhǎng)度)，這個(gè)圖靈機(jī)能在P(n)步內(nèi)給出回答，那么該問題稱作多項(xiàng)式時(shí)間可解的。

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

多項(xiàng)式時(shí)間歸約

假定給了兩個(gè)問題類q和q₀，如果存在一個(gè)確定型圖靈機(jī)M_q和一個(gè)多項(xiàng)式P，對(duì)于q中任意一個(gè)實(shí)例x，M_q都能在P(n)時(shí)間內(nèi)計(jì)算出q₀中一個(gè)實(shí)例y(其中n是實(shí)例x的編碼長(zhǎng)度)，使得x是q中有肯定回答的實(shí)例，當(dāng)且僅當(dāng)y是q₀中有肯定回答的實(shí)例，我們就說q多項(xiàng)式時(shí)間歸約到q₀。

NP完全問題

對(duì)于一個(gè)問題q₀，如果q₀屬于NP，且NP中任意一個(gè)問題，都能夠多項(xiàng)式時(shí)間歸約到q₀，則稱q₀為NP完全的，或q₀具有NP完全性。除巡回銷售員問題外，在實(shí)踐中還發(fā)現(xiàn)有大量的NP完全問題，它們來自計(jì)算機(jī)科學(xué)、數(shù)學(xué)、邏輯學(xué)等許多學(xué)科領(lǐng)域，總數(shù)已超過2000。下面是若干有代表性的NP完全問題。

（1）頂點(diǎn)覆蓋問題:給定一個(gè)圖G＝(V，E)，V為頂點(diǎn)集合，E為邊集合，又給定一個(gè)正整數(shù)K。問V是否有一個(gè)子集V′，其頂點(diǎn)數(shù)不超過K，并使G中每條邊都能被V′覆蓋，即每條邊的兩個(gè)頂點(diǎn)中至少有一個(gè)在V′中。

（2）三維匹配問題：三個(gè)班級(jí)，各有K人，共同參加某項(xiàng)活動(dòng)?；顒?dòng)中，要求三人一組，組中每班一人。三人彼此認(rèn)識(shí)的組稱為相識(shí)組。假定已知全部可能的相識(shí)組，問從中能否選出K個(gè)相識(shí)組，使得每人能參加且僅能參加一個(gè)相識(shí)組。

（3）分割問題：給定一堆自然數(shù)， 是否能將它們分成兩部分，使得這兩部分自然數(shù)各自的和彼此相等。

（4）帶優(yōu)先次序的調(diào)度問題:有m個(gè)處理機(jī)和一個(gè)任務(wù)集合，每個(gè)任務(wù)的執(zhí)行時(shí)間為1，已知任務(wù)間的優(yōu)先次序（不一定每對(duì)任務(wù)間都有優(yōu)先次序）和一個(gè)截止時(shí)間D。問是否有一個(gè)m個(gè)處理機(jī)的調(diào)度方法，滿足給定的優(yōu)先次序，且在截止時(shí)間D以前結(jié)束全部任務(wù)。

（5）可滿足性問題：對(duì)任意給定布爾表達(dá)式，是否可對(duì)式中各變?cè)x予真值和假值，使該表達(dá)式的值為真。

可滿足性問題是歷史上第一個(gè)NP完全問題，它由S.A.庫(kù)克于1971年提出。

意義

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

NP完全性的研究在實(shí)踐中有重要指導(dǎo)作用。在算法設(shè)計(jì)和分析過程中，如果已證明某問題是NP完全的，這就意味著面臨的是一個(gè)難于處理的問題。對(duì)于它，要找出一個(gè)在計(jì)算機(jī)上可行的（即多項(xiàng)式時(shí)間的）算法是十分困難的，甚至可能根本找不到(因?yàn)楹芸赡苡蠳P?P)。因此，對(duì)于NP完全問題，最好是去尋找近似解法，或者針對(duì)該問題的某些有實(shí)用價(jià)值的特殊情況，尋找多項(xiàng)式時(shí)間算法。

參考書目

1. 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.

建筑資質(zhì)代辦咨詢熱線：13198516101

標(biāo)簽：NP wanquanxing、NP完全性

版權(quán)聲明：本文采用知識(shí)共享 署名4.0國(guó)際許可協(xié)議 [BY-NC-SA] 進(jìn)行授權(quán)

文章名稱：《NP完全性》

文章鏈接：http://www.kaputelugumatrimony.com/12732.html

該作品系作者結(jié)合建筑標(biāo)準(zhǔn)規(guī)范、政府官網(wǎng)及互聯(lián)網(wǎng)相關(guān)知識(shí)整合。如若侵權(quán)請(qǐng)通過投訴通道提交信息，我們將按照規(guī)定及時(shí)處理。