計(jì)算理論與算法分析設(shè)計(jì)課件：NP完全性

CH7NP完全性

2024/7/22

of1587.1多項(xiàng)式時(shí)間歸約2024/7/23

of1582024/7/24

of158這些子句保證xi,j表示G的頂點(diǎn)之間的雙射2024/7/25

of1582024/7/26

of1582024/7/27

of158假設(shè)我們有帶有整數(shù)a1,a2,…,an和K的背包問題的實(shí)例。如果K=H=(Σai)/2,則規(guī)約需要做的所有工作就是從輸入里刪除K,所得出的劃分的實(shí)例等價(jià)于給定的背包問題的實(shí)例。當(dāng)然2024/7/28

of1582024/7/29

of1582024/7/210

of1582024/7/211

of1582024/7/212

of1582024/7/213

of1582024/7/214

of1582024/7/215

of1587.2cook定理定理7.2.2（Cook定理）可滿足性是NP完全的。2024/7/216

of158

2024/7/217

of1582024/7/218

of1582024/7/219

of158最大可滿足性：給定子句集F和整數(shù)K，是否存在滿足至少K個(gè)子句的真值賦值？定理7.2.4最大可滿足性是NP完全的。2024/7/220

of1582024/7/221

of1587.3其他的NP完全問題2024/7/222

of1587.3其他的NP完全問題

2024/7/223

of158定理7.3.1恰當(dāng)覆蓋是NP完全的。2024/7/224

of1582024/7/225

of1582024/7/226

of1582024/7/227

of1587.3.1旅行商問題定理7.3.2Hamilton圈是NP完全的。構(gòu)造上是給予具有關(guān)于Hamilton圈的有趣性質(zhì)的某種簡單圖，在NP完全性的術(shù)語里，這樣的圖被稱為小裝置。設(shè)想它是更大的圖G的一部分，通過畫成實(shí)心圓點(diǎn)的四個(gè)頂點(diǎn)，它連接到G的其余部分。換句話說，雖然存在其他的頂點(diǎn)和邊通向這個(gè)圖，但是除所畫出的邊外沒有任何別的邊與中間的三個(gè)頂點(diǎn)相關(guān)聯(lián)。另外假設(shè)G有Hamilton圈，即經(jīng)過G的每個(gè)頂點(diǎn)恰好一次的圈。2024/7/228

of1582024/7/229

of1582024/7/230

of1582024/7/231

of1582024/7/232

of1582024/7/233

of1582024/7/234

of158定理7.3.3無向Hamilton圈是NP完全的。2024/7/235

of1582024/7/236

of158定理7.3.4旅行商問題是NP完全的。2024/7/237

of1587.3.2劃分與團(tuán)恰當(dāng)覆蓋也提供了對劃分的NP完全性的良好證明。最容易的莫過于從密切相關(guān)的背包問題開始，其中給定要達(dá)到的任意的和K。定理7.3.5背包問題是NP完全的。2024/7/238

of1582024/7/239

of1582024/7/240

of1582024/7/241

of1582024/7/242

of158推論：劃分和雙機(jī)調(diào)度都是NP完全的。定理7.3.6獨(dú)立集是NP完全的。2024/7/243

of1582024/7/244

of15820