算法設計與分析 王紅梅 第二版 第10章 問題的復雜性

第10章問題的復雜性

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

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

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

類（Polynomial）問題。

所有易解問題都是P類問題P類問題和NP類問題非確定性算法與NP類問題

定義2.3

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

在這個階段，用一個確定性算法驗證：

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

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

P類問題和NP類問題2023/2/4第10章問題的復雜性13P類問題和NP類問題的主要差別：P類問題可以用多項式時間的確定性算法來進行判定或求解；NP類問題可以用多項式時間的非確定性算法來進行判定或求解。

P類問題和NP類問題2023/2/4第3章NP完全理論14NP完全問題的定義

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

定義3.6

令Π是一個判定問題，如果問題Π屬于NP類問題，并且對NP類問題中的每一個問題Π'

，都有Π'

∝pΠ，則稱判定問題Π是一個NP完全問題（NP

CompleteProblem），可以把NP完全問題記為NPC。

NP類問題NP完全問題問題Π問題Π'

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

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

（至今沒人證明）

P類問題：是可以用確定性算法在多項式時間內求解的一類問題。

NP類問題：是可以用非確定性算法在多項式時間猜測并驗證的一類問題，而且P?NP。

目前人們猜測P≠NP，則P類問題、NP類問題、NP完全問題之間的關系如下：

NP類問題P類問題NPC問題NP完全問題的定義

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

令Π是一個判定問題，如果對于NP類問題中的每一個問題Π'，都有Π'∝pΠ，則稱判定問題Π是一個NP難問題。

NP類問題NP難問題NP完全問題的定義

但問題Π不是NPC問題問題Π'

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

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

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

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

2023/2/4第3章NP完全理論20證明一個判定問題Π是NP完全問題需要經過兩步：

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

基本的NP完全問題

2023/2/4第3章NP完全理論21NP完全問題的證明思想NP類問題已知的NP完全問題要證明的NP完全問題基本的NP完全問題

問題Π'

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

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

2．獨立集問題（INDEPENDENTSETProblem）

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

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

基本的NP完全問題

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

多處理器調度問題MultiProcessorSchedulin

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

2023/2/4第3章NP完全理論25最大團問題（MaximumCliqueProblem）給定無向圖G=（V，E）、正整數k，判定圖中是否存在K個頂點，使得它們的導出子圖構成完全圖。10.哈密頓回路問