算法設(shè)計(jì)與分析 王紅梅 第二版 第10章 問(wèn)題的復(fù)雜性

第10章問(wèn)題的復(fù)雜性

算法設(shè)計(jì)與分析—本科生課程DesignandAnalysisofAlgorithm海南大學(xué)信息科學(xué)技術(shù)學(xué)院CollegeofInformationScienceandTechnology,HainanUniversity2023/2/4第10章問(wèn)題的復(fù)雜性2計(jì)算的限制算法作為求解問(wèn)題的方法，可以求解現(xiàn)實(shí)世界中的很多問(wèn)題，但有些問(wèn)題仍然無(wú)法用任何算法求解，有些問(wèn)題雖然有算法可以求解，但需要太長(zhǎng)的運(yùn)行時(shí)間或太大的存儲(chǔ)空間計(jì)算機(jī)學(xué)科的根本問(wèn)題是什么能被（有效地）自動(dòng)計(jì)算。圖靈：一個(gè)問(wèn)題是可計(jì)算的當(dāng)且僅當(dāng)它在圖靈機(jī)上經(jīng)過(guò)有限步驟后得到正確的結(jié)果。庫(kù)克：一個(gè)問(wèn)題是實(shí)際可計(jì)算的當(dāng)且僅當(dāng)它在圖靈機(jī)上經(jīng)過(guò)多項(xiàng)式步驟后得到正確的結(jié)果。易解問(wèn)題：多項(xiàng)式時(shí)間內(nèi)可解。難解問(wèn)題：指數(shù)時(shí)間求解。2023/2/4第10章問(wèn)題的復(fù)雜性3不可解問(wèn)題UnsolubleProblem難解問(wèn)題雖沒(méi)找到多項(xiàng)式時(shí)間算法，但按指數(shù)時(shí)間算法的難解問(wèn)題至少在理論上可以用計(jì)算機(jī)求解。但有些問(wèn)題不論耗多少時(shí)間也不能用計(jì)算機(jī)求解。不能用計(jì)算機(jī)求解（不論耗費(fèi)多少時(shí)間）的問(wèn)題稱為不可解問(wèn)題算法的極限2023/2/4第10章問(wèn)題的復(fù)雜性4例：不可解問(wèn)題典型例子：停機(jī)問(wèn)題（haltingproblem）算法的極限BoolHalt(char*prog,char*input){if(prog對(duì)輸入input停止執(zhí)行)returntrue;elsereturnfalse;}VoidContrary(char*prog){do result=Halt(prog,prog);while(result==true);}2023/2/4第10章問(wèn)題的復(fù)雜性5判定問(wèn)題DecisionProblem判定問(wèn)題是僅僅要求回答“yes”或“no”的問(wèn)題。很多實(shí)際問(wèn)題可以轉(zhuǎn)化為一系列更容易研究的判定問(wèn)題。舉例如下：P類(lèi)問(wèn)題和NP類(lèi)問(wèn)題2023/2/4第10章問(wèn)題的復(fù)雜性6例1：排序問(wèn)題排序問(wèn)題的判定形式可敘述為：給定一個(gè)整數(shù)數(shù)組，是否可以按非降序排列例2：圖著色問(wèn)題圖著色問(wèn)題的判定形式可敘述為：給定無(wú)向連通圖G=（V，E）和一個(gè)正整數(shù)k，是否可以用k種顏色為G中所有頂點(diǎn)著色，使得任何兩個(gè)相鄰頂點(diǎn)著色不同。例3：TSP問(wèn)題TSP問(wèn)題的判定形式可敘述為：P類(lèi)問(wèn)題和NP類(lèi)問(wèn)題2023/2/4第10章問(wèn)題的復(fù)雜性7給定一個(gè)帶權(quán)圖G=（V，E）和一個(gè)正整數(shù)k，是否有一個(gè)經(jīng)過(guò)所有頂點(diǎn)一次且僅一次再回到出發(fā)點(diǎn)的回路，其總距離小于k。例4：哈密頓回路問(wèn)題哈密頓回路問(wèn)題的判定形式可敘述為：在圖G=（V，E）中，是否有一個(gè)回路經(jīng)過(guò)所有頂點(diǎn)一次且僅一次再回到出發(fā)點(diǎn)。判定問(wèn)題的重要特性——驗(yàn)證比求易P類(lèi)問(wèn)題和NP類(lèi)問(wèn)題2023/2/4第10章問(wèn)題的復(fù)雜性8即在計(jì)算上對(duì)問(wèn)題求解是困難的，但在計(jì)算上判定一個(gè)待定解是否解決了該問(wèn)題卻是簡(jiǎn)單的。例1：求“哈密頓回路問(wèn)題”是難解問(wèn)題但驗(yàn)證一個(gè)給定頂點(diǎn)序列是不是“哈密頓回路”卻很容易，即只需要檢查前n個(gè)頂點(diǎn)是否互不相同，而最后一個(gè)頂點(diǎn)與第一個(gè)頂點(diǎn)是否相同例2：求大整數(shù)S=49770428644836899的因子是個(gè)難問(wèn)題但要驗(yàn)證a=223092871是不是大整數(shù)S的因子卻很容易。只要將S除以這個(gè)因子，余數(shù)為0即可P類(lèi)問(wèn)題和NP類(lèi)問(wèn)題2023/2/4第10章問(wèn)題的復(fù)雜性9例3：求線性方程組的解可能很困難，但驗(yàn)證一組解是否是方程組的解卻很容易，只要將這組解代入方程組中，然后驗(yàn)證是否滿足這組方程即可。確定性算法與P類(lèi)問(wèn)題定義2.1

設(shè)A是求解問(wèn)題Π的一個(gè)算法，如果在算法的整個(gè)執(zhí)行過(guò)程中，每一步只有一個(gè)確定的選擇，則稱算法A是確定性（Determinism）算法。P類(lèi)問(wèn)題和NP類(lèi)問(wèn)題2023/2/4第10章問(wèn)題的復(fù)雜性10定義2.2

如果對(duì)于某個(gè)判定問(wèn)題Π，存在一個(gè)非負(fù)整數(shù)k，對(duì)于輸入規(guī)模為n的實(shí)例，能夠以O(shè)(nk)的時(shí)間運(yùn)行一個(gè)確定性算法，得到y(tǒng)es或no的答案，則該判定問(wèn)題Π是一個(gè)P

類(lèi)（Polynomial）問(wèn)題。

所有易解問(wèn)題都是P類(lèi)問(wèn)題P類(lèi)問(wèn)題和NP類(lèi)問(wèn)題非確定性算法與NP類(lèi)問(wèn)題

定義2.3

設(shè)A是求解問(wèn)題Π的一個(gè)算法，如果算法A以如下猜測(cè)并驗(yàn)證的方式工作，就稱算法A是非確定性（Nondeterminism）算法：2023/2/4第10章問(wèn)題的復(fù)雜性11猜測(cè)階段在這個(gè)階段，對(duì)問(wèn)題的輸入實(shí)例產(chǎn)生一個(gè)任意字符串y，在算法的每一次運(yùn)行時(shí)，串y的值可能不同，因此，猜測(cè)以一種非確定的形式工作。驗(yàn)證階段

在這個(gè)階段，用一個(gè)確定性算法驗(yàn)證：

①檢查在猜測(cè)階段產(chǎn)生的串y是否是合適的形式，如果不是，則算法停下來(lái)并得到no；②如果串y是合適的形式，則驗(yàn)證它是否是問(wèn)題的解，如果是，則算法停下來(lái)并得到y(tǒng)es，否則算法停下來(lái)并得到no。P類(lèi)問(wèn)題和NP類(lèi)問(wèn)題2023/2/4第10章問(wèn)題的復(fù)雜性12定義2.4

如果對(duì)于某個(gè)判定問(wèn)題Π，存在一個(gè)非負(fù)整數(shù)k，對(duì)于輸入規(guī)模為n的實(shí)例，能夠以O(shè)(nk)的時(shí)間運(yùn)行一個(gè)非確定性算法，得到y(tǒng)es或no的答案，則該判定問(wèn)題Π是一個(gè)NP類(lèi)（NondeterministicPolynomial）問(wèn)題。

P類(lèi)問(wèn)題和NP類(lèi)問(wèn)題2023/2/4第10章問(wèn)題的復(fù)雜性13P類(lèi)問(wèn)題和NP類(lèi)問(wèn)題的主要差別：P類(lèi)問(wèn)題可以用多項(xiàng)式時(shí)間的確定性算法來(lái)進(jìn)行判定或求解；NP類(lèi)問(wèn)題可以用多項(xiàng)式時(shí)間的非確定性算法來(lái)進(jìn)行判定或求解。

P類(lèi)問(wèn)題和NP類(lèi)問(wèn)題2023/2/4第3章NP完全理論14NP完全問(wèn)題的定義

問(wèn)題背景大量問(wèn)題都具有下列特性存在多項(xiàng)式時(shí)間的非確定性算法，但是不知道是否存在多項(xiàng)式的確定性算法。同時(shí)不能證明這些問(wèn)題中的任何一個(gè)不存在多項(xiàng)式時(shí)間的確定性算法，這類(lèi)問(wèn)題就是NP完全問(wèn)題。2023/2/4第3章NP完全理論15NP完全問(wèn)題的定義

定義3.6

令Π是一個(gè)判定問(wèn)題，如果問(wèn)題Π屬于NP類(lèi)問(wèn)題，并且對(duì)NP類(lèi)問(wèn)題中的每一個(gè)問(wèn)題Π'

，都有Π'

∝pΠ，則稱判定問(wèn)題Π是一個(gè)NP完全問(wèn)題（NP

CompleteProblem），可以把NP完全問(wèn)題記為NPC。

NP類(lèi)問(wèn)題NP完全問(wèn)題問(wèn)題Π問(wèn)題Π'

2023/2/4第3章NP完全理論16NPC是NP類(lèi)問(wèn)題中最難的一類(lèi)問(wèn)題，其中任一個(gè)問(wèn)題至今都沒(méi)有找到多項(xiàng)式時(shí)間算法。NPC問(wèn)題：NPC有一個(gè)特質(zhì)：如果一個(gè)NPC問(wèn)題能在多項(xiàng)式時(shí)間內(nèi)得到解決，那么NPC中的每個(gè)問(wèn)題都可以在多項(xiàng)式內(nèi)求解多年的研究表明，目前還沒(méi)有一NPC問(wèn)題有多項(xiàng)式時(shí)間算法。這些問(wèn)題也許存在多項(xiàng)式時(shí)間算法，但還有待發(fā)現(xiàn)；這些問(wèn)題也許根本就不存在多項(xiàng)式時(shí)間算法，但目前缺乏足夠的技術(shù)來(lái)證明這一點(diǎn)。NP完全問(wèn)題的定義

2023/2/4第3章NP完全理論17P≠NP？P＝NP？

（至今沒(méi)人證明）

P類(lèi)問(wèn)題：是可以用確定性算法在多項(xiàng)式時(shí)間內(nèi)求解的一類(lèi)問(wèn)題。

NP類(lèi)問(wèn)題：是可以用非確定性算法在多項(xiàng)式時(shí)間猜測(cè)并驗(yàn)證的一類(lèi)問(wèn)題，而且P?NP。

目前人們猜測(cè)P≠NP，則P類(lèi)問(wèn)題、NP類(lèi)問(wèn)題、NP完全問(wèn)題之間的關(guān)系如下：

NP類(lèi)問(wèn)題P類(lèi)問(wèn)題NPC問(wèn)題NP完全問(wèn)題的定義

2023/2/4第3章NP完全理論18定義2.7

令Π是一個(gè)判定問(wèn)題，如果對(duì)于NP類(lèi)問(wèn)題中的每一個(gè)問(wèn)題Π'，都有Π'∝pΠ，則稱判定問(wèn)題Π是一個(gè)NP難問(wèn)題。

NP類(lèi)問(wèn)題NP難問(wèn)題NP完全問(wèn)題的定義

但問(wèn)題Π不是NPC問(wèn)題問(wèn)題Π'

2023/2/4第3章NP完全理論19

如果Π是NP完全問(wèn)題，Π’是NP難問(wèn)題，那么，他們之間的差別在于Π必定是NP類(lèi)問(wèn)題，而Π’不一定在NP類(lèi)問(wèn)題中。

一般而言，若判定問(wèn)題屬于NP完全問(wèn)題，則相應(yīng)的最優(yōu)化問(wèn)題屬于NP難問(wèn)題。例1：判定圖G=（V，E）中是否存在哈密頓回路是NPC問(wèn)題而求哈密頓回路中最短路徑的TSP問(wèn)題是NP難問(wèn)題例2：判定圖G=（V，E）中是否存在k個(gè)頂點(diǎn)團(tuán)的問(wèn)題是NPC問(wèn)題而求圖中頂點(diǎn)數(shù)最多的團(tuán)問(wèn)題則是NP難問(wèn)題

NP完全問(wèn)題和NP難問(wèn)題的區(qū)別：NP完全問(wèn)題的定義

2023/2/4第3章NP完全理論20證明一個(gè)判定問(wèn)題Π是NP完全問(wèn)題需要經(jīng)過(guò)兩步：

（1）證明問(wèn)題Π屬于NP類(lèi)問(wèn)題，也就是說(shuō)，可以在多項(xiàng)式時(shí)間以確定性算法驗(yàn)證一個(gè)任意生成的串，以確定它是不是問(wèn)題的一個(gè)解；（2）證明NP類(lèi)問(wèn)題中的每一個(gè)問(wèn)題都能在多項(xiàng)式時(shí)間變換為問(wèn)題Π。由于多項(xiàng)式問(wèn)題變換具有傳遞性，所以，只需證明一個(gè)已知的NP完全問(wèn)題能夠在多項(xiàng)式時(shí)間變換為問(wèn)題Π。

基本的NP完全問(wèn)題

2023/2/4第3章NP完全理論21NP完全問(wèn)題的證明思想NP類(lèi)問(wèn)題已知的NP完全問(wèn)題要證明的NP完全問(wèn)題基本的NP完全問(wèn)題

問(wèn)題Π'

2023/2/4第3章NP完全理論221971年，Cook通過(guò)Cook定理證明了SAT（合取范式的可滿足）問(wèn)題是NPC問(wèn)題1972年，Karp證明了十幾個(gè)問(wèn)題都是NPC的，以后在此基礎(chǔ)上又證明了幾千個(gè)NPC這些證明思想和技巧的累積極大的豐富了NP完全理論?；镜腘P完全問(wèn)題

2023/2/4第3章NP完全理論23其它NP完全問(wèn)題：1．三著色問(wèn)題（3_ColoringProblem）給定無(wú)向圖G=(V,E)，是否可用三種顏色來(lái)為圖G著色，使得圖中不會(huì)有兩個(gè)鄰接頂點(diǎn)具有同一種顏色。

2．獨(dú)立集問(wèn)題（INDEPENDENTSETProblem）

給定無(wú)向圖G=(V,E)，是否存在一個(gè)大小為k的獨(dú)立集S。其中，若其中任意兩個(gè)頂點(diǎn)都不互相鄰接，則稱S是圖G的獨(dú)立集。3．劃分問(wèn)題（

PARTITIONProblem）給定一個(gè)具有n個(gè)整數(shù)的集合S，是否能把S劃分成兩個(gè)子集S1和S2，使得S1中的整數(shù)之和等于S2中的整數(shù)之和。

基本的NP完全問(wèn)題

2023/2/4第3章NP完全理論244.子集求和問(wèn)題SUBSETSUM：給定整數(shù)集S和整數(shù)t，是否存在S的一個(gè)子集，使得T中的整數(shù)之和為t。5．裝箱問(wèn)題BINPACKING給定大小為S1,S2,…,Sn的物體，箱子的容量為C，以及一個(gè)正整數(shù)k，是否能夠用k個(gè)箱子來(lái)裝這n個(gè)物體。7.

多處理器調(diào)度問(wèn)題MultiProcessorSchedulin

給定m個(gè)性能相同的處理器、n個(gè)作業(yè)J1,J2,…,Jn、及每一個(gè)作業(yè)的運(yùn)行時(shí)間t1,t2,…,tn、以及時(shí)間T，是否可以調(diào)度這個(gè)處理器，使得它們最多在時(shí)間T里完成這個(gè)作業(yè)?；镜腘P完全問(wèn)題

2023/2/4第3章NP完全理論25最大團(tuán)問(wèn)題（MaximumCliqueProblem）給定無(wú)向圖G=（V，E）、正整數(shù)k，判定圖中是否存在K個(gè)頂點(diǎn)，使得它們的導(dǎo)出子圖構(gòu)成完全圖。10.哈密頓回路問(wèn)