基本NP完全問(wèn)題的證明.ppt

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

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

2、題的實(shí)例之集合3SAT表示三可滿(mǎn)足性問(wèn)題的實(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)含三個(gè)因子因此F′也是項(xiàng)的集合，所以F′是公式。由上兩式可見(jiàn):邏輯變量集合U增加一些變量，再改寫(xiě)公式F的每一項(xiàng)為項(xiàng)集合，就得到三可滿(mǎn)足問(wèn)題的實(shí)例。還需證明F′是可滿(mǎn)足的充分必要條件為F是可滿(mǎn)足的。5為定義映射g，只

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

4、Cj

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

6、2，yj}，{z1，z2，?yj}}即C′j含兩項(xiàng)。將Cj一個(gè)項(xiàng)替換為兩個(gè)項(xiàng).注意:這兩個(gè)項(xiàng)窮盡一個(gè)邏輯變量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個(gè)邏輯變量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,則增一個(gè)變量第一項(xiàng)和最后一項(xiàng)各含兩個(gè)z(原變量)和一個(gè)y(新增變量).其余各項(xiàng)含一個(gè)z和兩個(gè)y(其中一個(gè)是因子的非)10顯然，映射g為3SAT問(wèn)題計(jì)算一個(gè)實(shí)例所需時(shí)間為m和n的多項(xiàng)式。要增加n個(gè)變量集合,對(duì)應(yīng)F中的n個(gè)項(xiàng).每個(gè)集合至多含m-3個(gè)變量,m為U中因子的個(gè)數(shù)要把n個(gè)項(xiàng)改寫(xiě)為n個(gè)項(xiàng)集合每個(gè)集合至多含m-2個(gè)項(xiàng),每項(xiàng)有三個(gè)因子.11現(xiàn)在證明如F可滿(mǎn)足,則F′也可滿(mǎn)足.設(shè)f：U→{真,假}能使F值為真。因U是U′的子集,只須證明f可以

10、擴(kuò)展為f′：U′→{真,假}并使公式F′為真；從而只要給諸U′j的各邏輯變量賦值保持U的邏輯變量的賦值不變,并使F′為真即可12因集合(U′－U)中的邏輯變量被劃分為集合U′j，U′j中的邏輯變量?jī)H出現(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)滿(mǎn)足Cj，則f′不論給yj1,yj2賦什么值都能使C′j滿(mǎn)足。14②K=2，同樣可用數(shù)理邏輯證明C′j和Cj恒等，即C′j的值只與z1，z2有關(guān)，因f

11、已經(jīng)滿(mǎn)足Cj，則不論f給yj賦什么值,都可使C′j滿(mǎn)足15③K=3，(P9)U′j為空，且C′j只含一個(gè)項(xiàng),就是Cj,已被f滿(mǎn)足。Cj已經(jīng)含三個(gè)因子,被f賦值，因此f,不用給任何新邏輯變量賦值。16④K>3，Cj={z1,z2,…,zk}，因f已滿(mǎn)足Cj，此即Cj的K個(gè)因子中至少一個(gè)為真，設(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=