基本NP完全問題的證明.ppt

《基本NP完全問題的證明.ppt》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、§5.6基本NP完全問題的證明1定理1三可滿足問題(3SAT)是NP完全問題。(證)整個證明過程分成兩步，先證3SAT∈NP，再證明SAT∝3SAT．3SAT∈NP是顯然的，因?yàn)楹苋菀讟?gòu)造一不確定算法，該算法第一階段猜一個函數(shù)f：U→{真,假}。2然后，第二階段檢測公式F的值，這只需將公式F中的所有因子u及?u分別用f(u)和f(u)的補(bǔ)替代，即用“真”或“假”替代，再對邏輯式求值。容易看出，第二階段所需時間是m和n的多項(xiàng)式其中m是集合U的邏輯變量的個數(shù)，n是公式F的項(xiàng)的個數(shù)。3SAT∝3SAT就不那末明顯了。先構(gòu)造映射g：SAT→3SAT其中SAT表示可滿足性問

2、題的實(shí)例之集合3SAT表示三可滿足性問題的實(shí)例的集合。然后再證明g是多項(xiàng)式轉(zhuǎn)換。SAT的實(shí)例為①集合U＝{u1,u2,…,um}②公式F＝{c1,c2,…,cn}，其中ci(i＝1，2，…，n)是項(xiàng)。以U及F為輸入，g為3SAT構(gòu)造實(shí)例U′及F′如下所述:4U′=U∪U′1∪U′2∪…∪U′nF′=C′1∪C′2∪…∪C′n其中C′j是項(xiàng)的集合，且每一項(xiàng)含三個因子因此F′也是項(xiàng)的集合，所以F′是公式。由上兩式可見:邏輯變量集合U增加一些變量，再改寫公式F的每一項(xiàng)為項(xiàng)集合，就得到三可滿足問題的實(shí)例。還需證明F′是可滿足的充分必要條件為F是可滿足的。5為定義映射g，只

3、須說明如何構(gòu)造C′j及U′j.公式F的項(xiàng)Cj是因子的集合Cj＝{Z1，Z2，…，ZK}即

4、Cj

5、＝K，Cj由K個因子組成。C′j及U′j的構(gòu)成按K的值分四種情況討論。6K＝l，Cj＝{z1}，則U′j及C′j構(gòu)造為U′j＝{yj1,yj2}增加兩個邏輯變量而已C′j＝{{z1,yj1,?yj2},{z1,?yj1,yj2},{z1,yj1,yj2},{z1,?yj1,?yj2}}即C′j含四個項(xiàng)。將Cj一個項(xiàng)替換為四個項(xiàng).注意:這四個項(xiàng)窮盡兩個邏輯變量yj1,yj2的四種情況7K＝2，Cj＝{z1，z2}，則U′j＝{yj}僅僅增加一個邏輯變量C′j＝{{z1，z

6、2，yj}，{z1，z2，?yj}}即C′j含兩項(xiàng)。將Cj一個項(xiàng)替換為兩個項(xiàng).注意:這兩個項(xiàng)窮盡一個邏輯變量yj的兩種情況8K＝3，Cj＝{z1，z2，z3}，則U′j＝Φ不增加邏輯變量C′j＝{{z1，z2，z3}}即C′j含一項(xiàng)。9K>3，Cj＝{z1,z2,…,zk}，則U′j＝{yj1,yj2,…,yjk-3},增加K-3個邏輯變量C′j＝{{z1,z2,yj1},{z3,?yj1,yj2},{z4,?yj2,yj3},…,{zi-1,?yji-3,yji-2},{zi,?yji-2,yji-1},{zi+1,?yji-1,yji},…,{zk-2,?yj

7、k-4,yjk-3},{zk-1,zk,?yjk-3}}即C′j含(K一2)項(xiàng),比

8、U′j

9、大1。若K=4,則含兩項(xiàng).若K=4,則增一個變量第一項(xiàng)和最后一項(xiàng)各含兩個z(原變量)和一個y(新增變量).其余各項(xiàng)含一個z和兩個y(其中一個是因子的非)10顯然，映射g為3SAT問題計算一個實(shí)例所需時間為m和n的多項(xiàng)式。要增加n個變量集合,對應(yīng)F中的n個項(xiàng).每個集合至多含m-3個變量,m為U中因子的個數(shù)要把n個項(xiàng)改寫為n個項(xiàng)集合每個集合至多含m-2個項(xiàng),每項(xiàng)有三個因子.11現(xiàn)在證明如F可滿足,則F′也可滿足.設(shè)f：U→{真,假}能使F值為真。因U是U′的子集,只須證明f可以

10、擴(kuò)展為f′：U′→{真,假}并使公式F′為真；從而只要給諸U′j的各邏輯變量賦值保持U的邏輯變量的賦值不變,并使F′為真即可12因集合(U′－U)中的邏輯變量被劃分為集合U′j，U′j中的邏輯變量僅出現(xiàn)在相應(yīng)的C′j中,因此只須證明，映射f′可以逐次擴(kuò)展到各集合U′j，每次擴(kuò)展使C′j中的項(xiàng)的值都為真．13同樣分四種情況，①K＝1，用數(shù)理邏輯的方法很容易證明C′j和Cj恒等，(P7)即C′j的值只與z1有關(guān)，因f已經(jīng)滿足Cj，則f′不論給yj1,yj2賦什么值都能使C′j滿足。14②K=2，同樣可用數(shù)理邏輯證明C′j和Cj恒等，即C′j的值只與z1，z2有關(guān)，因f

11、已經(jīng)滿足Cj，則不論f給yj賦什么值,都可使C′j滿足15③K=3，(P9)U′j為空，且C′j只含一個項(xiàng),就是Cj,已被f滿足。Cj已經(jīng)含三個因子,被f賦值，因此f,不用給任何新邏輯變量賦值。16④K>3，Cj={z1,z2,…,zk}，因f已滿足Cj，此即Cj的K個因子中至少一個為真，設(shè)zi為真，按i的值分三種情況,討論如何擴(kuò)展映射f17(ⅰ)i為1或2，則令yj1=yj2=…=yjK-3=假這使C′j的每一項(xiàng)都為真。(ⅱ)如i為K－4或K－3，則令yj1=yj2=…=yjK-3=真這也使C′j的每一項(xiàng)都為真。(ⅲ)如2

12、ji-2=