第四節(jié)．計算復(fù)雜性理論介紹(參考版)
2024-09-09 15:24本頁面
【正文】 ＊理論上 nnf ?)( 與 nnf 10)( ? 沒什么差別，但是在應(yīng)用上會有所不同 參考書： “ NP 問題與優(yōu)化問題” 。 （不僅僅用于比較算法，主要用于研究問題本身）。 52 nn ? （ n 取一定值），一般 2n? ~3n ，或大部分情況（線性規(guī)劃中單純形方法）。 八、總結(jié) 。 七、 NP難題 21 ??? , ????1 完全問題 . 2? 是 NP 難的 (不管 ????2 是否滿足。即一個問題解決了，其它問題也就解決了。 ??? ，則 1? 是 NP完全的。否則 goto 2. 例 2： A? : 旅行商判定問題 B? : 旅行商問題 A? 的算法： B? 算法求最小路徑 1l ??1l ? 存在二類簡化： a: ?????????? ABAB , b: BBAB ????????? , 至少和 A? 一樣難 . B? 解決了 A?? 也解決了 NP 完全 判定問題 ????1 ；對所有其它判定問題 ????39。 3. 將最高成績排在第一，從 S 中去掉該學(xué)生成績 ? 新S 。 A? 的算法： 1. S={1, … , n 個學(xué)生成績 }。 所以有“ P = NP？” 或“ P? NP？” 感覺上， NP 中元素更多，傾向 P? NP. 問題 A 對于問題 B是多項式歸約可簡化的： A 的算法中要調(diào)用 B
公司管理相關(guān)推薦
鄂ICP備17016276號-1