最近有人問什麼是NP 什麼是NPComplete
就順便查了一下清楚的定義
簡單的說，
NP hard的問題就是沒有辦法找到Polynomial的演算法來解決此問題
但是在NP hard的問題中又可以分成 NP Complete 跟 Weakly NP
原因是演算法複雜度包含了兩個部分
一個是演算法迭代的operation次數
一個是演算法的digits 次數
如果兩個都是NP的話，就是NP Complete
如果演算法是Polynomial的話，但是digit有可能會爆掉
就是weakly NP
參考:
http://en.wikipedia.org/wiki/Weakly_NP-complete
http://en.wikipedia.org/wiki/NP-complete
沒有留言:
張貼留言