np完整性理論ppt課件(編輯修改稿)
2025-06-01 18:18 本頁面
【文章內(nèi)容簡(jiǎn)介】 nTO 定理 84 對(duì)于問題 P的任何長(zhǎng)度為 n的輸入，設(shè)求解問題 P的算法 A在 RAM模型下，不含有乘法和除法指令，且按對(duì)數(shù)耗費(fèi)標(biāo)準(zhǔn)其時(shí)間復(fù)雜性為 ，那么，算法 A在 k帶圖靈機(jī)模型 TM下的時(shí)間復(fù)雜性為 。 )(nT))(( 2 nTO18 問題變換與計(jì)算復(fù)雜性歸約 具體地說 ， 假設(shè)有 2個(gè)問題 A和 B， 將 問題 A變換為問題 B是指： (1)將問題 A的輸入變換為問題 B的適當(dāng)輸入 。 (2)解出問題 B。 (3)把問題 B的輸出變換為問題 A的正確解 。 若用 O(τ(n)) 時(shí)間能完成上述變換的第 (1)步和第 (3)步 ， 則稱問題 A是 τ(n) 時(shí)間可變換到問題 B， 且簡(jiǎn)記為 A∝ τ(n) B。 其中的 n通常為問題 A的規(guī)模 (大小 )。 當(dāng) τ(n) 為 n的多項(xiàng)式時(shí)，稱問題 A可在多項(xiàng)式時(shí)間內(nèi)變換為問題 B。特別地，當(dāng) τ(n) 為 n的線性函數(shù)時(shí)，稱問題 A可線性地變換為問題 B。 通過問題變換的技巧，可以將 2個(gè)不同問題的計(jì)算復(fù)雜性聯(lián)系在一起。這樣就可以將一個(gè)問題的計(jì)算復(fù)雜性歸結(jié)為另一個(gè)問題的計(jì)算復(fù)雜性，從而實(shí)現(xiàn)問題的計(jì)算復(fù)雜性歸約。 19 問題變換與計(jì)算復(fù)雜性歸約 命題 1(計(jì)算時(shí)間下界歸約 )：若已知問題 A的計(jì)算時(shí)間下界為 T(n)， 且問題 A是 τ(n) 可變換到問題 B， 即 A∝ τ(n) B， 則 T(n)O(τ(n)) 為問題 B的一個(gè)計(jì)算時(shí)間下界。 命題 2(計(jì)算時(shí)間上界歸約 )：若已知問題 B的計(jì)算時(shí)間上界為 T(n)， 且問題 A是 τ(n) 可變換到問題 B， 即 A∝ τ(n) B， 則T(n)+O(τ(n)) 是問題 A的一個(gè)計(jì)算時(shí)間上界。 問題的變換與問題的計(jì)算復(fù)雜性歸約的關(guān)系 ： 在命題 1和命題 2中，當(dāng) τ(n)=o(T(n)) 時(shí)，問題 A的下界歸約為問題 B的下界，問題 B的上界歸約為問題 A的上界。 20 問題變換與計(jì)算復(fù)雜性歸約 通過問題變換獲得問題的計(jì)算時(shí)間下界的例子 ： (1)判別函數(shù)問題：給定 n個(gè)實(shí)數(shù) ，計(jì)算其判別函數(shù) 。 nxxx ,..., 21?? ?ji ji xx )( 元素惟一性問題可以在 O(1)時(shí)間內(nèi)變換為判別函數(shù)問題。任何一個(gè)計(jì)算判別函數(shù)的算法，計(jì)算出判別函數(shù)值后，再作一次測(cè)試，判斷其值是否為 0，即可得到元素惟一性問題的解。由命題 1即知，元素惟一性問題的計(jì)算時(shí)間下界 也是判別函數(shù)問題的一個(gè)計(jì)算時(shí)間下界。 )log( nn? (2)最接近點(diǎn)對(duì)問題：給定平面上 n個(gè)點(diǎn)，找出這 n個(gè)點(diǎn)中距離最近的 2個(gè)點(diǎn)。 在元素惟一性問題中，將每一個(gè)實(shí)數(shù) ， 1≤ i≤n ， 變換為平面上的點(diǎn) ( ， 0)， 1≤ i≤n ， 則元素惟一性問題可以在線性時(shí)間內(nèi)變換為最接近點(diǎn)對(duì)問題。 ixix21 P類與 NP類問題 ? 非確定性圖靈機(jī) ? P類與 NP類語言 ? 多項(xiàng)式時(shí)間驗(yàn)證 22 非確定性圖靈機(jī) 非確定性圖靈機(jī)（ NDTM ） ：一個(gè) k帶的非確定性圖靈機(jī) M是一個(gè) 7元組： (Q， T， I， δ ， b， q0， qf)。 與確定性圖靈機(jī)不同的是非確定性圖靈機(jī)允許移動(dòng)函數(shù) δ 具有不確定性 ，即對(duì)于 Q?Tk中的每一個(gè)值 (q。x1,x2,… ,xk)， 當(dāng)它屬于 δ 的定義域時(shí)， Q?(T?{L，R， S})k中有惟一的一個(gè) 子集 δ(q。x 1,x2,… ,xk)與之對(duì)應(yīng)?？梢栽讦?q。x 1,x2,… ,xk)中隨意選定一個(gè)值作為它的函數(shù)值。 在圖靈機(jī)計(jì)算模型中，移動(dòng)函數(shù) δ 是單值的 ，即對(duì)于 Q?Tk中的每一個(gè)值，當(dāng)它屬于 δ 的定義域時(shí)， Q?(T?{L， R， S})k中只有惟一的值與之對(duì)應(yīng)，稱這種圖靈機(jī)為 確定性圖靈機(jī) ，簡(jiǎn)記為DTM(Deterministic Turing Machine)。 23 P類與 NP類語言 P類和 NP類語言的定義： P={L|L是一個(gè)能在 多項(xiàng)式時(shí)間內(nèi) 被一臺(tái) DTM所接受的語言 } NP={L|L是一個(gè)能在 多項(xiàng)式時(shí)間 內(nèi)被一臺(tái) NDTM所接受的語言 } 由于一臺(tái)確定性圖靈機(jī)可看作是非確定性圖靈機(jī)的特例，所以可在多項(xiàng)式時(shí)間內(nèi)被確定性圖靈機(jī)接受的語言也可在多項(xiàng)式時(shí)間內(nèi)被非確定性圖靈機(jī)接受。故 P ? NP。 24 P類與 NP類語言 NP類語言舉例 —— 無向圖的團(tuán)問題 。 該問題的輸入是一個(gè)有 n個(gè)頂點(diǎn)的無向圖
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1