算法設(shè)計與分析-鐘

1、CH6 計算復(fù)雜性 6.1 P類問題分類理論上能用算法解決的P類: 有有效算法的理論上不能用算法解決的NP類: 無有效算法的26.1 P類3丘奇-圖靈論題的定量細(xì)化如下：多項式界限的TM和P類分別適當(dāng)刻畫了實際可行算法和實際可解問題的直覺概念。 定理6.1.1 P在補運算下封閉證明：如果語言L被多項式界限的TM M判定，那么它的補被交換M的y和n得到的TM M判定。故多項式界限不受影響。6.1 P類46.1 P類5P是多項式可判定語言的類嚴(yán)格地說，只包含語言所有正則語言都屬于 P問題與語言的關(guān)系？6.2 若干問題66.2 若干問題問題的定義：問題是(無窮)輸入的集合 + 對每個輸入問的判定性(

2、是或否)問題例：可達性輸入集是所有三元組(G, vi, vj) 的集合，其中G是有窮圖, vi, vj是G的兩個頂點。問題是在G里是否存在從vi到vj的路徑76.2 若干問題可達性是否屬于P?嚴(yán)格說，P只包含語言，所以與可達性無關(guān)語言是對問題的編碼。當(dāng)然，任何語言也被認(rèn)為是問題。問題和對應(yīng)的語言是同一個事物的兩個不同方面語言更適合與Turing機相聯(lián)系問題更清楚陳述了與算法相關(guān)的實際計算任務(wù)86.2 若干問題：可達性問題可達性問題的語言描述：R=k(G)b(i)b(j)：在G中有從vi到vj的路徑b(i)是整數(shù)i的二進制編碼k(G)是G的字符串編碼可達性屬于P，即語言R屬于P 計算G的自反傳遞

3、閉包，這可用(n3) 時間里完成檢查G的自反傳遞閉包里對應(yīng)vj 和vj 的項，它告訴我們在G里是否存在從vi到vj的路徑96.2 若干問題：可達性問題106.2 若干問題:歐拉圖 圖G是歐拉圖當(dāng)且僅當(dāng) ：對任意一對都不是孤立的頂點u, vV，存在從u到v的通路 所有頂點都有同樣數(shù)目的入邊和出邊歐拉圖對應(yīng)的語言L = k(G)：G是歐拉圖驗證歐拉圖：在多項式時間里確定是否除孤立點外所有頂點都連通。方法是先計算圖的自反傳遞閉包，再驗證是否除孤立點外所有頂點都連通驗證是否所有頂點都有同樣數(shù)目的入邊和出邊，也可在多項式時間里完成歐拉圖屬于P116.2 若干問題：優(yōu)化問題優(yōu)化問題要求的不是“是”或“否”

4、的回答要求從許多可行解里找出最好的（根據(jù)成本函數(shù)）可轉(zhuǎn)變?yōu)檎Z言形式：給每個輸入加上成本函數(shù)的界限旅行商問題給定整數(shù) n2，n n距離矩陣dij，以及整數(shù)預(yù)算B0，是否存在1, 2, , n的排列使得c() B。126.2 若干問題：優(yōu)化問題獨立集給定無向圖G和整數(shù) K2，是否存在V的子集C滿足 |C|K，使得對所有vi,vjC，在vi和vj間沒有邊？團給定無向圖G和整數(shù) K2，是否存在V的子集C滿足 |C|K，使得對所有vi,vjC，在vi和vj間有邊？頂點覆蓋給定無向圖G和整數(shù) K2，是否存在V的子集C滿足 |C|K，使得C覆蓋G的所有邊？13尚未找到多項式時間算法整數(shù)劃分1415B(7)亦

5、含數(shù)字151，等于所有數(shù)字和的一半復(fù)雜度：O(nH)整數(shù)劃分166.3 布爾可滿足性176.3 布爾可滿足性186.3 布爾可滿足性對這個問題，至今沒有已知的多項式時間算法，并且人們普遍相信不存在這樣的算法。19二元可滿足性:所有子句只有兩個或更少文字的公式6.3 布爾可滿足性 假設(shè)在公式里存在只有一個文字的子句 ，比方說第三個子句(x1) 。那么顯然這個文字在任何滿足的真值賦值里都必須是T。即在本例中立即決定T(x1)=T，然后繼續(xù)進行。既然我們知道T(x1)=T，我們就從公式里刪除包含x1作為文字的所有子句，因為這些子句已經(jīng)被滿足了（在本例中我們刪除第一個子句）。不過如果子句包含否定文字，

6、那么我們就從子句里刪除這個文字，因為這個文字是因此它不能用來滿足子句。20 我們把尋找單文字子句直到不存在這樣的子句為止的過程稱為清洗 。如果在清洗的任何一步產(chǎn)生了空子句, 即假定因為對某個 i, 單文字子句及其否定都在前一步出現(xiàn), 那么我們說清洗已經(jīng)失敗。假定我們的公式在每個子句里恰有兩個文字。選擇還沒有賦真值的任何變元，試驗設(shè)置它的真值是T并完成清洗；然后把公式恢復(fù)原狀，把同一個變元設(shè)置成并再次完成清洗。若兩次清洗都失敗則搜索結(jié)束，公式是不可滿足的。若兩次清洗中至少有一次成功，則設(shè)置變元等于成功的清洗中的真值并繼續(xù)。6.3 布爾可滿足性216.3 布爾可滿足性因為算法對每個變元最多完成兩遍

7、清洗并且每遍清洗都在多項式時間里完成，所以由此得出二元可滿足性屬于P。226.4 NP類對非確定型TM判定語言L的含義: 對每個不屬于L的輸入，機器的所有計算都必須拒絕輸入；對每個屬于L的輸入，我們僅僅要求存在至少一個計算接受輸入只要存在一個接受計算，在其余的計算里就可以沒有、或有些、或大多數(shù)、或全部都拒絕這個輸入。23非確定型TM在給定輸入上所有可能的計算最好是畫成樹的結(jié)構(gòu)。頂點表示格局，向下的線表示步。非確定性選擇表示成有多條線離開的頂點。用垂直維度量時間。6.4 NP類246.4 NP類例6.4.1 可滿足性屬于NP已經(jīng)證明過不屬于P設(shè)計在多項式非確定性時間里判定可滿足布爾公式的所有編碼

8、的非確定性Turing機M，對于輸入w步1：計算w中出現(xiàn)的變元個數(shù)n，同時向第2條帶上填入變元名的字符串 In （P）步2：非確定性階段，把第2條帶上所有I變元改寫為T或。每個變元的取值是非確定的步3：對每種I的賦值序列進行驗證，是否可滿足 （P）M滿足 NP，且給出y或n的判定256.4 NP類例6.4.2 旅行商問題也屬于NP給定整數(shù) n2，n n距離矩陣dij，以及整數(shù)預(yù)算B0，是否存在1, 2, , n的排列使得c() B。證明這個結(jié)論的非確定型TM M在第二條帶上非確定性地寫與輸入的長度相等的0,1和|_|的字符串然后機器進入確定性階段，其中它驗證寫在第二條帶上的字符串是否碰巧是整數(shù)

9、1, , n的雙射的編碼，其中，n是給定輸入里的城市數(shù)。雙射編碼成用二進制寫的(1), (2), , 用|_|分隔。若字符串確實是雙射的編碼，則機器繼續(xù)確定性地計算巡回路線的成本，并且與輸入里的“預(yù)算”比較。若成本不超過B，則機器接受 ；在所有其他的最終結(jié)局里（若所猜測的字符串不是雙射的編碼，或者若它表示成本大于B的巡回路 線）這臺機器都拒絕。顯然字符串屬于這臺機器所判定的語言當(dāng)且僅當(dāng)它編碼旅行商問題的 “是”實例 。26同理 ，容易證明我們在前一節(jié)遇到的其它明顯的困難問題都屬于NP ，包括獨立集哈密頓圈劃分等非確定性 “算法” 聰明地利用了在非確定性時間界限計算的定義里的基本非對稱性它們在獨

10、立的計算里試驗所處理的問題的所有可能解，一旦發(fā)現(xiàn)可行解就立即接受它，忘掉其他的非可行解。6.4 NP類276.4 NP類28PNP？是復(fù)雜性理論里具有核心重要性的目前還懸而未決的問題NPEXP？是另一個懸而未決的問題，不過重要性要低一些。但是我們確實知道下列結(jié)論：在包含關(guān)系之鏈 P NP EXP里，第三個類真包含第一個類。雖然我們猜想上面顯示的兩個包含關(guān)系都是包含，但是目前我們能證明的全部東西就是其中至少一個是真包含，而且我們不知道是哪個。6.4 NP類29為判定可滿足性和旅行商問題設(shè)計的TM很類似首先非確定性地產(chǎn)生字符串，然后確定性地驗證所產(chǎn)生的字串是否具有與輸入相關(guān)的某種需要的性質(zhì)。若輸入

11、屬于這個語言則至少存在一個合適的字符串。若輸入不屬于這個語言則找不到具有所需要性質(zhì)的字符串。這樣的字符串稱為證書，或者見證。所有NP里的問題都有證書 ，并且只有NP里的問題才有證書 。6.4 NP類: 證書30證書必須是多項式那么短的，即它的長度最多是輸入長度的多項式。還必須是在多項式時間里可驗證的。在可滿足性的情形里驗證證書就是要求驗證真值賦值是否滿足輸入公式的所有子句；在旅行商問題的情形里就是要求驗證建議的巡回路線的總成本是否在預(yù)算之內(nèi)；對于獨立集就是驗證給定的頂點集是否大小合適并且在它們之間沒有邊等等。最后，問題的所有“是”輸入都必須有至少一個證書，而所有“否”輸入都必須沒有任何證書。6.4 NP類: 證書310/1背包問題給定背包問題的實例a1, a2, an和K, 滿足 ip ai=K的1, , n的子集P可作為對給定實例的回答是 “是”的證書。它是多項式短的，并且它可在多項式時間里通過二進制加法來驗證。6.4 NP類: 證書32簡短的證書示例：合數(shù)集合 CN4 294 967 297 是否合數(shù)？不存在有效方法，但每一個屬于C的數(shù)確實有簡短的證書6 700 417和641可作為4