C**********n
发帖数: 100 | 1 不是说背包问题是经典的NP问题吗，
可是为什么还有动态规划的解法呢？该解法的时间复杂度肯定不是指数。 |
y*******g
发帖数: 6599 | 2 复杂度和输出还有关啊.
【在 C**********n 的大作中提到】
: 不是说背包问题是经典的NP问题吗，
: 可是为什么还有动态规划的解法呢？该解法的时间复杂度肯定不是指数。
|
C**********n
发帖数: 100 | 3 绛紫阿，
加上输出就是指数了吗？
【在 y*******g 的大作中提到】
: 复杂度和输出还有关啊.
|
l********s
发帖数: 358 | 4 pseudo-polynormial
【在 C**********n 的大作中提到】
: 不是说背包问题是经典的NP问题吗，
: 可是为什么还有动态规划的解法呢？该解法的时间复杂度肯定不是指数。
|
C**********n
发帖数: 100 | 5 你是说该解法是伪多项式吗？
我还是不明白为什么要加个伪字呢？
【在 l********s 的大作中提到】
: pseudo-polynormial
|
f*********r
发帖数: 68 | 6 Knapsack runs in O(nW), where n is the # of items, and W is the weight. If W
=O(n), then it's polynominal, but what if W=O(2^n)??? So in general case it
is NPC.
【在 C**********n 的大作中提到】
: 你是说该解法是伪多项式吗？
: 我还是不明白为什么要加个伪字呢？
|
C**********n
发帖数: 100 | 7 哦，明白一点了，呵呵。多谢。
W
it
【在 f*********r 的大作中提到】
: Knapsack runs in O(nW), where n is the # of items, and W is the weight. If W
: =O(n), then it's polynominal, but what if W=O(2^n)??? So in general case it
: is NPC.
|
l********s
发帖数: 358 | 8 Yes. It's weak NPC.
【在 y*******g 的大作中提到】
: 复杂度和输出还有关啊.
|
y*******g
发帖数: 6599 | 9 谢谢 刚看到google证明了 .
【在 l********s 的大作中提到】
: Yes. It's weak NPC.
|
g*******y
发帖数: 1930 | 10 真巧，正好今天我们算法课上老师正好说了这个问题。
NPC是指对输入规模而言。一个数字W的输入规模是N = logW
【在 C**********n 的大作中提到】
: 不是说背包问题是经典的NP问题吗，
: 可是为什么还有动态规划的解法呢？该解法的时间复杂度肯定不是指数。
|
|
|
i******t
发帖数: 370 | 11 It means polynomaial to the value of the input, in this case O(nW), but non-
polynomial to the length of the input. You only need logW bits to encode
weight W.
【在 C**********n 的大作中提到】
: 你是说该解法是伪多项式吗？
: 我还是不明白为什么要加个伪字呢？
|
r****o
发帖数: 1950 | 12 请问，那有没有复杂度为O(nW)但又不是NPC的算法(不一定针对背包问题)呢？
W
it
【在 f*********r 的大作中提到】
: Knapsack runs in O(nW), where n is the # of items, and W is the weight. If W
: =O(n), then it's polynominal, but what if W=O(2^n)??? So in general case it
: is NPC.
|
g*******y
发帖数: 1930 | 13 大数分解就没被证明是NPC吧
否则的话，peter shor的大数分解量子算法，不就已经解决的NP=P的问题了
【在 r****o 的大作中提到】
: 请问，那有没有复杂度为O(nW)但又不是NPC的算法(不一定针对背包问题)呢？
:
: W
: it
|
f*********r
发帖数: 68 | 14 peter shor的大数分解量子算法, 是适用于量子计算机的, 我们一般说的NP和P指是Non
-deterministic和 deterministic图灵机的, 它们根本不是一个概念范筹, 好像还有其
它的一些计算机模型. 即使你证明了大数分解是NPC的, 也不能说NP=P.
【在 g*******y 的大作中提到】
: 大数分解就没被证明是NPC吧
: 否则的话，peter shor的大数分解量子算法，不就已经解决的NP=P的问题了
|
r****o
发帖数: 1950 | 15 假定某个算法复杂度O(nW),
什么时候我们需要考虑W很大的情况呢？
W
it
【在 f*********r 的大作中提到】
: Knapsack runs in O(nW), where n is the # of items, and W is the weight. If W
: =O(n), then it's polynominal, but what if W=O(2^n)??? So in general case it
: is NPC.
|
f*********r
发帖数: 68 | 16 好像要具体分析n和W都代表什么, 才能决定.
【在 r****o 的大作中提到】
: 假定某个算法复杂度O(nW),
: 什么时候我们需要考虑W很大的情况呢？
:
: W
: it
|
g*******y
发帖数: 1930 | 17 正因为这样，所以如果大数分解是NPC，那么就证明了量子计算体系是对经典计算模型
的质的超越。
可惜目前已知的量子算法，最多都只能解决某些NP的问题。
我没有听说过有其他的计算模型。不知道我记对了没，貌似所有经典(物理意义上的“
经典”:非量子的)的计算模型，都能由图灵机/随机的图灵机等价。
Non
【在 f*********r 的大作中提到】
: peter shor的大数分解量子算法, 是适用于量子计算机的, 我们一般说的NP和P指是Non
: -deterministic和 deterministic图灵机的, 它们根本不是一个概念范筹, 好像还有其
: 它的一些计算机模型. 即使你证明了大数分解是NPC的, 也不能说NP=P.
|
