CH7NP完全性

定義7.1.1如果存在計算函數(shù)f:**的多項(xiàng)式界限的Turing機(jī)M，那么f稱為多項(xiàng)式時間可計算的。設(shè)語言L1,L2*，設(shè)f:**是多項(xiàng)式時間可計算的函數(shù)。如果對每個x*下列關(guān)系成立：xL1ifff(x)

L2，那么f稱為從L1到L2的多項(xiàng)式歸約。7.1多項(xiàng)式時間規(guī)約ABff7.1多項(xiàng)式時間規(guī)約問題的多項(xiàng)式時間歸約f在多項(xiàng)式時間內(nèi)把問題A的實(shí)例變換成B的實(shí)例記為：APB歸約的含義：A的求解難度不大于B；或者：如果B有效可解，則A有效可解問題B至少與A一樣難AffB一般而言，象f(A)僅是B的一個子集，且f(*\A)是*\B的子集7.1多項(xiàng)式時間規(guī)約7.1多項(xiàng)式時間規(guī)約例7.1.1從Hamilton圈到可滿足性的多項(xiàng)式時間歸約Hamilton圈：給定圖G，經(jīng)過G的每個頂點(diǎn)恰好一次的圈

問題：給定Hamilton圈的實(shí)例G

V

V，V={1,2,…,n}。描述算法f，它產(chǎn)生合取范式形式的布爾公式f(G)，使得G有Hamilton圈ifff(G)是可滿足的構(gòu)造布爾公式f(G)f(G)包含n2個布爾變元：xij，其中1≤i,j≤n，代表含義：G的頂點(diǎn)i是G的Hamilton圈上的第j個頂點(diǎn)f(G)的各個子句用布爾邏輯去表示Hamilton圈必須滿足的各種要求7.1多項(xiàng)式時間規(guī)約構(gòu)造布爾公式f(G)Hamilton圈的第j個位置上至少出現(xiàn)一個頂點(diǎn)。即對j=1,…,n，有子句：Hamilton圈的第j個位置上只能出現(xiàn)一個頂點(diǎn)，故加入O(n3)個如下形式的子句，其中i,j,k=1,…,n且i≠k：頂點(diǎn)i恰有一次出現(xiàn)在圈上這些子句保證xi,j表示G的頂點(diǎn)之間的雙射圈上第j個位置恰好出現(xiàn)一個頂點(diǎn)7.1多項(xiàng)式時間規(guī)約構(gòu)造布爾公式f(G)為f(G)設(shè)計表達(dá)此置換是G的圈的子句j=1,…,n和每對不是G的邊的頂點(diǎn)(i,k)，加入子句：公式(1)要求：若不存在邊(i,k)，則圈上相繼的兩個頂點(diǎn)（第j和j+1個）不能為i與kf(G)的構(gòu)造可在多項(xiàng)式時間完成含O(n3)個子句含O(n3)個文字7.1多項(xiàng)式時間規(guī)約證明G有Hamilton圈iff布爾公式f(G)可滿足當(dāng)存在f(G)的可滿足真值賦值T，則G有Hamilton圈存在一個n個頂點(diǎn)的排列每一個i恰有一個T(xi,j)為真每一個j恰有一個T(xi,j)為真在此頂點(diǎn)的排列中，由公式(1)知相繼的兩個點(diǎn)間有邊存在故此方向?yàn)檎娈?dāng)G有Hamilton圈，則存在f(G)的可滿足真值賦值TG的Hamilton圈定義了一個頂點(diǎn)的排列，且相鄰兩點(diǎn)間有邊相連由此對應(yīng)的真值賦值T使f(G)的所有子句滿足7.1多項(xiàng)式時間規(guī)約引理7.1.1若f1是從L1到L2的多項(xiàng)式歸約，且f2是從L2到L3的多項(xiàng)式歸約，那么它們的合成f1?f2是從L1到L3的多項(xiàng)式歸約。證明：f1?f2從L1到L3的多項(xiàng)式可計算函數(shù)設(shè)f1用TMM1在多項(xiàng)式時間p1里計算設(shè)f2同TMM2在多項(xiàng)式時間p2里計算則f1?f2可用機(jī)器M1M2計算，在輸入x*上M1M2輸出f1?f2(x)，所用時間不超過多項(xiàng)式p1(|x|)+

p2(p1(|x|))xL1ifff1?f2(x)L3xL1

ifff1(x)L2

f1(x)L2ifff2(f1(x))=f1?f2(x)L37.1多項(xiàng)式時間規(guī)約定義7.1.2設(shè)L*是語言，如果LNP，并且對每一個語言L’NP，存在從L’到L的多項(xiàng)式歸約

那么L稱為是NP完全(NP-Complete)的7.1多項(xiàng)式時間規(guī)約定理7.1.1設(shè)L是NP完全語言。那么

P=NPiffLP證明：：假設(shè)P=NP。因?yàn)長是NP完全的，所以LNP，故LP：L是NP完全語言，且LP，說明其可用確定型TMM1在多項(xiàng)式時間p1(n)里判定。需要證明，任意L’，若L’NP則L’P根據(jù)NPC定義，存在從L’到L的多項(xiàng)式歸約f。設(shè)f使用TMM2在多項(xiàng)式時間p2(n)里計算由引理7.1.1知：TMM2M1在多項(xiàng)式時間里判定L’M1：多項(xiàng)式時間完成LP的歸約M2：多項(xiàng)式時間完成L’L的歸約故M2M1在多項(xiàng)式時間內(nèi)完成L’P的歸約7.2Cook定理定理7.2.2（Cook定理）可滿足性是NP完全的。一旦證明了第一個NPC問題，即可通過多項(xiàng)式歸約來證明其它問題亦屬于NPC問題第一個NPC問題的證明需要證明所有NP問題都可歸約到它Cook在1971年證明了第一個NPC問題：可滿足性7.2Cook定理定理7.2.3三元可滿足性是NP完全的完全性證明：將可滿足性歸約到三元可滿足性構(gòu)造從任意子句集F出發(fā)，在多項(xiàng)式時間里得到等價的三元子句集t(F)的歸約函數(shù)等價性：t(F)是可滿足的iffF是可滿足的

7.2Cook定理等價性：t(F)是可滿足的iffF是可滿足的假設(shè)存在賦值T滿足t(F)，證明T也滿足F的每個子句反證法，設(shè)該賦值T使F中的所有k個文字都為假假設(shè)存在賦值T滿足F，證明T可被擴(kuò)充成滿足t(F)的賦值T’構(gòu)造T’最大可滿足性：給定子句集F和整數(shù)K，是否存在滿足至少K個子句的真值賦值？定理7.2.4最大可滿足性是NP完全的。把可滿足性歸約到最大可滿足性可滿足性是最大可滿足性的特例：K等于子句個數(shù)給定可滿足性帶有m個子句的實(shí)例F，通過僅僅向F附加容易計算的參數(shù)K=m，我們構(gòu)造最大可滿足性的等價實(shí)例(F,m)存在至少滿足F的K=m個子句的真值賦值iff存在滿足F的所有子句的真值賦值157.2Cook定理167.3其它NP完全問題

7.3其它NP完全問題7.3其它NP完全問題定理7.3.1恰當(dāng)覆蓋是NP完全的證明略18定理7.3.2Hamilton圈是NP完全的。構(gòu)造性證明將恰當(dāng)覆蓋問題(U,F)多項(xiàng)式時間歸約到有向圖G=t(U,F)，使得G有Hamilton圈iff(U,F)有恰當(dāng)覆蓋構(gòu)造一種稱為小裝置的簡單圖，它是更大圖G的一部分7.3其它NP完全問題構(gòu)造性證明構(gòu)造一種稱為小裝置的簡單圖，它是更大圖G的一部分構(gòu)造

G=t(U,F)，其中U={u1,…,un}以及F={S1,…,Sm}G的頂點(diǎn)：u1,…,un以及S1,…,Sm，外加頂點(diǎn)u0和S0G的邊：對

i=1,…,m，存在兩條邊(Si-1,Si)，一條稱為長邊，一條為短邊G的邊：對j=1,…,n，在頂點(diǎn)uj-1和uj之間添加若干條邊，邊數(shù)與包含元素uj的F里的集合一樣多；即邊(uj-1,uj)的每個復(fù)制品對應(yīng)于uj在集合Si里的一次出現(xiàn)G的邊：添加邊(un,S0)和(Sm,u0)，構(gòu)成封閉的圈利用小裝置“異或”子圖，把邊(uj-1,uj)的這個復(fù)制品與長的邊(Si-1,Si)相連7.3其它NP完全問題構(gòu)造性證明構(gòu)造一種稱為小裝置的簡單圖，它是更大圖G的一部分構(gòu)造

G=t(U,F)，其中U={u1,…,un}以及F={S1,…,Sm}7.3其它NP完全問題構(gòu)造性證明證明圖G=t(U,F)有Hamilton圈iff(U,F)有恰當(dāng)覆蓋假設(shè)存在恰當(dāng)覆蓋C。可在圖中構(gòu)造Hamilton圈：對所有SiC，經(jīng)過(Si-1,Si)的短邊；其它Si經(jīng)過長邊對每個元素uj，經(jīng)過(uj-1,uj)的復(fù)制品，它對應(yīng)于包含的C里面的唯一集合7.3其它NP完全問題構(gòu)造性證明證明圖G=t(U,F)有Hamilton圈iff(U,F)有恰當(dāng)覆蓋假設(shè)存在Hamilton圈，可找出恰當(dāng)覆蓋：設(shè)C是Hamilton圈經(jīng)過的短邊(Si-1,Si)的集合；證明C是合法的集合覆蓋根據(jù)“異或”子圖的性質(zhì)，C里的集合Si中的元素恰恰是形如(uj-1,uj)的邊的復(fù)制品，這些邊都被Hamilton圈經(jīng)過對每個元素ujU，Hamilton圈恰好經(jīng)過一條這樣的邊，故每個元素ujU恰好被包含在一個屬于C的集合里7.3其它NP完全問題定理7.3.6獨(dú)立集是NP完全的。證明將三元可滿足性問題F多項(xiàng)式時間歸約到

獨(dú)立集構(gòu)造無向圖G和整數(shù)K，使得在G里存在K個頂點(diǎn)并且在它們之間沒有邊iffF是可滿足的對于F的每個子句，在G里生成三角形，且頂點(diǎn)對應(yīng)于子句Ci的文字兩個頂點(diǎn)用邊相連當(dāng)前僅當(dāng)它們的文字互為否定F含有m個子句，則G中有3m個頂點(diǎn)。目標(biāo)是K=m，等于子句數(shù)7.3其它NP完全問題證明構(gòu)造無向圖G和整數(shù)K，使得在G里存在K個頂點(diǎn)并且在它們之間沒有邊iffF是可滿足的給定滿足F的任意真值賦值T在每個三角中挑選對應(yīng)著被滿足的文字的頂點(diǎn)可獲得規(guī)模為m的獨(dú)立集假設(shè)G有K=m個頂點(diǎn)的獨(dú)立集I。同一