[理工] 演算法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