資源描述：
《算法分析與設計-2016-第4講.ppt》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。
1、算法分析與設計第4講-2016山東大學計算機學院/軟件學院上次內容：(1)確定型圖靈機與P類，DTM多項式時間可解的-----P類(2)非確定圖靈機與NP類，NP類----多項式時間可驗證的，或NTM多項式時間可計算的。注意：在定義時空復雜性時，我們只關心NTM程序計算回答為Yes的實例的時空復雜性?；卮鸱竦膶嵗魂P心。只是針對那些回答為Yes的實例定義時空復雜性，這樣定義足以滿足我們的需要。Rabin與Scott兩個人最先在IBM做的工作，最先定義的非確定計算。企圖把算法分為兩大類，多項式時間的和指數時間的，其實這
2、樣分類是有局限性的，不一定完美，但能說明問題。相隔了近30年！非確定圖靈機沒法實現！因為判定問題都可以當作一個語言的識別問題。一個語言：給定符號集?={0，1}，一個語言就是一個?*的子集L??*。判定一個x??*是否屬于L，即所謂判定問題。只能驗證一面?，SAT實例符號集合L，回答是的SAT實例集合判定：x??*，是否屬于L?1變換到?2，應該達到的目的：若?2存在多項式算法，則?1也有多項式算法。多項式變換(歸約)：?1=；?2=變換f：?1*??2*I?L1，f(I)?L
3、2，?1(I)=?2(f(I))f變換可以在p(
4、I
5、=n)時間內計算完成。則f稱為由?1到?2的多項式時間歸約。Reduction(1)非確定型圖靈機與驗證機還是不同的。(2)但是有一個結論：一個問題是多項式時間可驗證的，當且僅當它是非確定型圖靈機多項式時間可計算的。(3)Rabin與Scott兩個人最先在IBM做的工作。定義了非確定型計算，也就有了非確定型圖靈機。?2?1多項式算法多項式變換與NPC類，上次講到什么是多項式變換。我們需要什么？定義多項式變換，達到如下目標：R-S的非確定圖靈機的時間復雜性難定義。只
6、關心回答Yes的實例的時間就好說了。NP問題可以認為若實例回答是，則存在不確定多項式時間算法正確回答的判定問題類。*在定義NP問題時，只關心問題的那些回答Yes的實例。回答No的實例不關心。NP類：若對回答Yes的問題實例，存在NTM程序能夠多項式時間回答是，則這個問題就屬于NP類。*用不著關心那些回答No的實例。為什么？能夠達到目的了。前人就是這么定義的。若有實例I，猜測機猜測了一個解放到讀寫帶上，我們的程序驗證回答是，則可以回答I是一個回答是的實例；不需要定義的是回答否的那些實例：若猜測機猜測了一個解放到讀寫帶上
7、，我們的程序驗證回答否，不知道I是否是回答否的實例，所以干脆不定義！希望：若?1可以多項式歸約到?2，?2存在多項式算法，則?1也有多項式算法。前面的多項式歸約進一步修改如下：認為與前面的定義等價。只關心那些回答yes的實例了。?1=；?2=變換f：?(1)I?L1，f(I)?L2，(2)?1(I)=1???2(f(I))=1，充分必要的。I?Y(?1)??f(I)?Y(?2)。不關心回答No的實例。實際前面NTM定義中就只關心回答Yes的實例。(3)f變換可以在p(
8、I
9、=n
10、)時間內計算完成。?1?2*P問題可以在多項式時間回答是或否。*NP問題只能在多項式時間回答是。*P問題可以在多項式時間判定解的存在性。*NP問題只能多項式時間驗證解存在。*?1變換為?2，當然希望?2是多項式時間可計算的。引理3.1：若?1??2，?2?P，則?1?P。注意一點，當多項式可解時，否的實例也能在多項式時間回答。證明：回答是的實例能夠變換，回答否的實例也能夠變換。當?2?P時，是和否都能多項式時間回答。當然?1實例回答是和否也能多項式時間回答下面又要回憶前面的內容了！If(I)yesnoAlgI?Y(?
11、)I?N(?)?1?2再解釋非確定Turing機：規(guī)定(1)猜測部件把猜測的解寫在從-1開始向左的存儲帶上。(2)我們自己編寫的驗證程序直接使用帶方格[x,-1]中的猜測信息。(3)實際這不是最早(Rabin,Scott)的非確定型圖靈機版本。(4)NP問題，多種定義版本，多項式時間可驗證的，NTM多項式時間可求解的。該說明什么是NP-Complete問題了。期望：若有一個特殊NP問題?，任意一個NP問題均可多項式時間歸約到該問題，則該問題非常特殊，稱為NP-Complete問題。?要求是NP類問題。若NP-Comp
12、lete問題可以多項式時間解決，則其他所有NP問題都可以在多項式時間解決。所有NP問題都能多項式時間可解，這件事其實很大的重任。幾乎不可能的，所以NP-C問題多項式時間可解，也是不可能的。解釋：如果NP-C行，什么鳥都行！每個NP問題都存在多項式時間解答算法嗎？(1)首先要搞清楚，現在我們研究的問題是多項式時間可驗證的問題類，最后只需要回答是和
