作者DJWS (...)
看板Prob_Solve
標題[問題] 時間複雜度疑問
時間Wed Sep 28 15:27:55 2011
問題一：
Polynomial time algorithm 是指 O(n^k) 的演算法，
其中 n 我想應該是指資料的數量多寡，不是指資料的數值大小吧？
那麼為何 AKS primality test 的 n 是指數值大小呢？
^^^^^^^^
修正: 數值(二進位表示)的位數
問題二：
有一些 NP-complete 問題，例如 0/1 Knapsack Problem，
當輸入資料的數值大小範圍有限、又是整數時，
我們可以用 pseudo-polynomial time algorithm 解決問題。
那麼，同樣是 NP-complete 問題的 Hamiltonian path，
也會有 pseudo-polynomial time algorithm 嗎？
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.168.20.43
1F：推 ledia:1. 的 n 是指(二進位)位數, 不然傳統怎麼做都是 O(n) 09/28 17:08
2F：推 ledia:2. 的話, depends, 這也是 weakly/strongly NP-complete 09/28 17:12
3F：→ ledia: 的分野 09/28 17:13
4F：→ DJWS:我把問題一的敘述改好了~ 09/29 13:09
5F：→ DJWS:問題二，NP-Complete問題之間不是可以互相轉換嗎? 為何還會有 09/29 13:10
6F：→ DJWS:weakly/strongly的差異呢? 09/29 13:11
※ 編輯: DJWS 來自: 118.168.20.43 (09/29 13:12)
7F：→ suhorng:可是AKS我記得是lg ? 那就不是與長度成指數次方關係了？ 09/29 14:32
8F：推 singlovesong:N 正確的說法應該是input size 10/01 11:50
9F：推 ledia:NPC 的性質不變, weakly/strongly 的差別在於如果 input 的 10/02 15:33
10F：→ ledia:範圍是 bounded, 原本的問題能不能變簡單, 我理解成問題難度 10/02 15:34
11F：→ ledia:的另一種維度 10/02 15:34
12F：→ ledia:畢竟 reduction 並沒有保證 input 的 range 會不會仍然保有 10/02 15:35
13F：→ ledia: bounded 的性質 10/02 15:36