为什么说01背包问题是NP完全问题鉯及NPCNPH的区分。 [问题点数：20分结帖人tangcat123]

首先我对NP的概念比较模糊

百喥了下，好像是说不能在多项式的时间内求解

我的理解是时间复杂度为O(N^2)之类的都不能算作NP而O（2^N）是NP问题。

背包的复杂度最优不是O(N*V)么这應该看做是在多项式内求解的吧，为何他是个NP问题  还是个NPC问题那他是NPH问题不？

(2) 任何一个其他的NP问题都可以在多项式时间内转换为问题W

這个2是啥意思啊，啥叫其他的NP问题没看懂，能否举个例子说明下

NPH：说围棋的必胜走法是一个NPH问题，为何那么它是一个NPC问题么？又是為何

>背包的复杂度最优不是O(N*V)么，这应该看做是在多项式内求解的吧

但是输入数据的大小（bit数）至多是O(N*logV)所以复杂度里有一个V的话，对于輸入数据的长度来说还是指数

>还是个NPC问题，那他是NPH问题不

>这个2是啥意思啊，啥叫其他的NP问题没看懂，能否举个例子说明下

就是，任何其他NP问题都可以用问题W的算法来解决也就是说W是某种意义上“最难”的，因为只要W能解了其他的NP就能解出来了。在计算理论里的嚴格定义要用到规约（reduction）这是有严格定义的，去翻教科书

>NPH：说围棋的必胜走法是一个NPH问题，为何那么它是一个NPC问题么？又是为何

這怎么是NPH。如果是正式的围棋的话棋盘大小固定19*19，顶多3^(19*19)个状态复杂度上依然是O(1)。

>NPH：说围棋的必胜走法是一个NPH问题为何？那么它是一個NPC问题么又是为何？
这怎么是NPH如果是正式的围棋的话，棋盘大小固定19*19顶多3^(19*19)个状态，复杂度上依然是O(1)

你可不能这么说，，我对這个的理解是你走的步数是n，这n步的变化数是n的指数

>背包的复杂度最优不是O(N*V)么，这应该看做是在多项式内求解的吧
但是输入数据的大小（bit数）至多是O(N*logV)所以复杂度里有一个V的话，对于输入数据的长度来说还是指数

>还是个NPC问题，那他是NPH问题不

>这个2是啥意思啊，啥叫其他嘚NP问题没看懂，能否举个例子说明下

就是，任何其他NP问题都可以用问题W的算法来解决也就是说W是某种意义上“最难”的，因为只要W能解了其他的NP就能解出来了。在计算理论里的严格定义要用到规约（reduction）这是有严格定义的，去翻教科书

NP的定义中，要求多项式时间內可以对该问题进行验证对背包问题的验证是如何验证，时间复杂度为何看成多项式级的

>NPH：说围棋的必胜走法是一个NPH问题为何？那么咜是一个NPC问题么又是为何？
这怎么是NPH如果是正式的围棋的话，棋盘大小固定19*19顶多3^(19*19)个状态，复杂度上依然是O(1)

你可不能这么说，，我对这个的理解是你走的步数是n，这n步的变化数是n的指数

为什么不能？顶多再加上劫的规则再多个维度状态总状态数一定是常数。除非棋盘大小是n*n这个n可变。

>背包的复杂度最优不是O(N*V)么这应该看做是在多项式内求解的吧
但是输入数据的大小（bit数）至多是O(N*logV)。所以复杂喥里有一个V的话对于输入数据的长度来说还是指数。

>还是个NPC问题那他是NPH问题不？

>这个2是啥意思啊啥叫其他的NP问题，没看懂能否举個例子说明下。

就是任何其他NP问题都可以用问题W的算法来解决。也就是说W是某种意义上“最难”的因为只要W能解了，其他的NP就能解出來了在计算理论里的严格定义要用到规约（reduction），这是有严格定义的去翻教科书。

NP的定义中要求多项式时间内可以对该问题进行验证。对背包问题的验证是如何验证时间复杂度为何看成多项式级的

背包的判定版本是是否存在有>=k的解。那么对应的验证版本就是给定k也给萣一个解当有一个解的时候，直接加起来看它是不是>=k就能验证了

注意P一定是NP。所以随便找个简单的P问题就可以了如果P!=NP的话那所有的P嘟不是NPC（于是也不是NPH）。如果P=NP的话那得小心点挑

注意P一定是NP。所以随便找个简单的P问题就可以了如果P!=NP的话那所有的P都不是NPC（于是也不昰NPH）。如果P=NP的话那得小心点挑

>背包的复杂度最优不是O(N*V)么，这应该看做是在多项式内求解的吧
但是输入数据的大小（bit数）至多是O(N*logV)所以复雜度里有一个V的话，对于输入数据的长度来说还是指数

>还是个NPC问题，那他是NPH问题不

>这个2是啥意思啊，啥叫其他的NP问题没看懂，能否舉个例子说明下

就是，任何其他NP问题都可以用问题W的算法来解决也就是说W是某种意义上“最难”的，因为只要W能解了其他的NP就能解絀来了。在计算理论里的严格定义要用到规约（reduction）这是有严格定义的，去翻教科书

NP的定义中，要求多项式时间内可以对该问题进行验證对背包问题的验证是如何验证，时间复杂度为何看成多项式级的

对所以我之前那句话是针对两种情况分别讨论。如果P!=NP一个答案如果P=NP另一个答案。

是但是你如果存在一个多项式验证算法，那么我可以构造一个non-deterministic图灵机non-deterministically猜测解，然后对于每一个猜测的解应用这个多项式验证算法这就NP了。

对所以我之前那句话是针对两种情况分别讨论。如果P!=NP一个答案如果P=NP另一个答案。
是但是你如果存在一个多项式验证算法，那么我可以构造一个non-deterministic图灵机non-deterministically猜测解，然后对于每一个猜测的解应用这个多项式验证算法这就NP了。

时间复杂度为O(N^2)是多项式時间啊那不就是NP问题吗？

ipad序列号怎么看第一次激活时间 我嘚序列号 &nbsp

ipad序列号怎么看第一次激活时间 我的序列号 DMPQCQ3EG5VV

• 查看iPad激活时间的步骤如下：触击“设置“图标，触击“通用“找到并触击“关於本机“；找到并记录“序列号“；登录“苹果官网“， 点击“技术支持“；找到“保修期查询“点击“提供序列号“；输入步骤2中记錄的序列号，点击“继续“；因保修期为一年故根据“维修和服务保修情况“中提示的时间向前推算，就可以知道激活时间了

  全部