[理工] 107 成大 程設
想問一下這題，我的想法是所有NP問題因為都不難於NP-hard問題，所以都可以在p時間內
reduce到NP-hard
而題目說到NP-hard具P時間可解，那是否代表P=NP=NPC=NP-hard呢？還是僅有P=NP=NPC而
已？
謝謝！
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 112.104.18.31 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1607959809.A.743.html
推
12/15 00:00,
5年前
, 1F
12/15 00:00, 1F
→
12/15 01:43,
5年前
, 2F
12/15 01:43, 2F
→
12/15 01:46,
5年前
, 3F
12/15 01:46, 3F
→
12/15 01:57,
5年前
, 4F
12/15 01:57, 4F
我的想法是NP-C和NP-H差別是在能不能在P時間內被驗證，那如果題目提及NP-C可在P時間
內被解，是否等同說了NP-H能在P時間內被驗證？這樣NP-C和NP-H是否就屬同樣集合呢？
觀念有誤再麻煩糾正！謝謝！
※ 編輯: seafoodccu (223.138.43.120 臺灣), 12/15/2020 08:02:50
推
12/15 09:27,
5年前
, 5F
12/15 09:27, 5F
→
12/15 09:27,
5年前
, 6F
12/15 09:27, 6F
→
12/15 09:27,
5年前
, 7F
12/15 09:27, 7F
→
12/15 09:28,
5年前
, 8F
12/15 09:28, 8F
→
12/15 09:28,
5年前
, 9F
12/15 09:28, 9F
推
12/15 09:31,
5年前
, 10F
12/15 09:31, 10F
→
12/15 09:31,
5年前
, 11F
12/15 09:31, 11F
a大我想問一下，為什麼NP-H都可以在p時間內解了，卻不能用p驗證？解出解來不就也是
驗證了解對不對嗎？
※ 編輯: seafoodccu (112.104.18.31 臺灣), 12/15/2020 09:52:24
推
12/15 10:11,
5年前
, 12F
12/15 10:11, 12F
→
12/15 10:11,
5年前
, 13F
12/15 10:11, 13F
→
12/15 10:14,
5年前
, 14F
12/15 10:14, 14F
→
12/15 13:44,
5年前
, 15F
12/15 13:44, 15F
→
12/15 13:45,
5年前
, 16F
12/15 13:45, 16F
所以，NP-H就算能在P時間內解出，也不代表它能在P時間內驗證答案嗎？
※ 編輯: seafoodccu (112.104.18.31 臺灣), 12/15/2020 14:22:24
→
12/15 14:29,
5年前
, 17F
12/15 14:29, 17F
推
12/17 11:18,
5年前
, 18F
12/17 11:18, 18F
→
12/17 11:19,
5年前
, 19F
12/17 11:19, 19F
→
12/17 11:20,
5年前
, 20F
12/17 11:20, 20F
→
12/17 11:22,
5年前
, 21F
12/17 11:22, 21F
→
12/17 11:22,
5年前
, 22F
12/17 11:22, 22F
→
12/17 13:25,
5年前
, 23F
12/17 13:25, 23F