算法設(shè)計(jì)與分析第七章隨機(jī)算法及計(jì)算復(fù)雜性-資料下載頁
2025-01-06 18:36本頁面
【正文】 定問題。 NP難與 NP完全問題 P類和 NP類問題 ? 定義 如果對某個(gè)判定問題，存在著一個(gè)非負(fù)整數(shù) k，對輸入規(guī)模為 n的實(shí)例，能夠以O(shè)( nk)的時(shí)間運(yùn)行一個(gè)非確定性的算法，得到y(tǒng)es或 no的答案，則該判定問題 π是一個(gè) NP類判定問題。 ? 特性： 存在確定性的算法，能夠以多項(xiàng)式時(shí)間，來檢查和驗(yàn)證在推測階段產(chǎn)生的答案。 NP難與 NP完全問題 NP難問題 ? NP難 ? 定義 令 π是一個(gè)判定問題，如果對 NP中的每一個(gè)問題 π‘∈ NP ，有 ，就說判定問題 π是一個(gè) NP難題。 ??? p39。 NP難與 NP完全問題 NP完全問題 ? NP完全問題 ? 定義 令 π是一個(gè)判定問題，如果： ? (1) π∈ NP ，并且： ? (2) 對 NP中的所有問題 π‘∈ NP ，都有 ； 則稱判定問題 π是 NP完全的。 ??? p39。 NP難與 NP完全問題 ? NP難題和 NP完全問題的差別 ? π是 NP完全問題， π‘是 NP難題， ? 則 π必定在 NP類中，而 π‘不一定在 NP類中。 NP難與 NP完全問題 ? 歸約的傳遞性 ? 定理 令 、 和 是三個(gè)判定問題，滿足 ，及 ，則有 。 ? 39。? 39。39。?39。39。39。 ??? p ??? p39。??? p39。39。 NP難與 NP完全問題 ? NP完全問題的特性 ? 定理 令 和 是 NP中的兩個(gè)問題，使得 。如果 是 NP完全的，則 也是 NP完全的。 ? 39。???? p39。39。?? NP難與 NP完全問題 ? NP完全問題的證明： ? 證明下面兩件事情： ? (1) ，并且： ? (2) 存在一個(gè) NP完全問題 ，使得 ； NP????? p39。39。? NP難與 NP完全問題 ? 定理 （ Cook定理）可滿足性問題SATISFIABILITY是 NP完全的。 ? Cook定理的意義： ? Cook定理給出了第一個(gè) NP完全問題，使得對任何問題，只要能夠證明 ，并且SATISFIABILITY ，那么 ，就是NP完全的 NP???? p ? NP難與 NP完全問題 ? 部分的 NP完全問題樹 SA T I SF I A B IL I T Y 3 _ SA T I SFI A BIL IT Y CL Q U E H A M _ CY CL E V E R T E X _ CO V E R T RA _ SA L E SMA N SU BSE T _ SU M NP難與 NP完全問題 ? 通常認(rèn)為的 P、 NP、 NP Complete、 NP Hard問題的關(guān)系： P NP NP Complete NP Hard NP難與 NP完全問題 ? NP完全問題的特性為：當(dāng)且僅當(dāng)所有其它 NP完全問題可以在多項(xiàng)式時(shí)間內(nèi)求解，該問題可以在多項(xiàng)式時(shí)間內(nèi)求解。 ? 如果一個(gè) NP難問題可以在多項(xiàng)式時(shí)間內(nèi)求解，則所有的 NP完全問題都可以在多項(xiàng)式時(shí)間內(nèi)求解。 ? NP完全和 NP難問題都不是多項(xiàng)式時(shí)間可解的。
電大資料相關(guān)推薦
鄂ICP備17016276號(hào)-1