[理工] 算法reduce问题 joy7658x348 PTT批踢踢实业坊

[理工] 算法reduce问题

楼主: joy7658x348 (joy7658x348) 2017-11-16 17:53:16

大家好
想请问一题：
Suppose problem P1 can be reduce to Problem P2,and we know P2 is NP-hard. Is P
1 also np-hard?
我认为是对的。
毕竟就算P1是NPC那也是包含在NP-hard问题里面
不知道这样观念是否正确？
或者认为否的原因是为什么呢？
谢谢大家考试加油！

楼主: joy7658x348 (joy7658x348) 2017-11-16 18:54:00

答案是错。因为P1也可能是P问题～刚刚被同学解惑了谢谢各位

作者: alan23273850 2017-11-16 19:50:00

只要记得是从简单reduce到难的就不会弄错了因为如果难的可以transform到简单的，这个过程便称为solve而不是reduce

继续阅读

[理工] 算法kobebset105 [理工] 线代朱敏德(周易) 证明|AB|=|A|*|B|JKLee [理工] 资料压缩两题问题请教lady012266 [理工] 离散逻辑问题nO25948 [理工] OS process vs. threads9e0ay917 [理工] 线代线性映射证明写法问题hopixar [理工] OS 几题问题TMDTMD2487 [理工] OS 关于Virtual MachineTMDTMD2487 [理工] 104台大资工资演kobebset105 [理工] 99台联大电机计组 memory accessdefsrisars