[問題] 時間複雜度疑問

[DJWS (...)]

問題一：

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
推 ledia:1. 的 n 是指(二進位)位數, 不然傳統怎麼做都是 O(n)
推 ledia:2. 的話, depends, 這也是 weakly/strongly NP-complete
→ ledia:   的分野
→ DJWS:我把問題一的敘述改好了~
→ DJWS:問題二，NP-Complete問題之間不是可以互相轉換嗎? 為何還會有
→ DJWS:weakly/strongly的差異呢?
※ 編輯: DJWS            來自: 118.168.20.43        (09/29 13:12)
→ suhorng:可是AKS我記得是lg ? 那就不是與長度成指數次方關係了？
推 singlovesong:N 正確的說法應該是input size
推 ledia:NPC 的性質不變, weakly/strongly 的差別在於如果 input 的
→ ledia:範圍是 bounded, 原本的問題能不能變簡單, 我理解成問題難度
→ ledia:的另一種維度
→ ledia:畢竟 reduction 並沒有保證 input 的 range 會不會仍然保有
→ ledia: bounded 的性質