作者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