推 asd3136396: 我覺得是全部在同一個集合12/15 00:00
→ mathtsai: NP-H可解->NP-C可解-> P = NP12/15 01:43
→ mathtsai: NP-C會包含在 P=NP 裡12/15 01:46
我的想法是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
推 alex391a: Np hard 會在p 但因為定義不會在np(雖然這很怪）https:/12/15 09:27
→ alex391a: /i.imgur.com/GRbdGsX.jpg12/15 09:27
→ alex391a: 全部問題都可以用p解決 但np hard不能用p驗證 所以 npc=12/15 09:28
→ alex391a: np 12/15 09:28
推 alex391a: 樓上那樣畫的話np hard就沒在p裡面了 我這樣理解應該沒12/15 09:31
→ alex391a: 有錯吧 12/15 09:31
a大我想問一下，為什麼NP-H都可以在p時間內解了，卻不能用p驗證？解出解來不就也是
驗證了解對不對嗎？
※ 編輯: seafoodccu (112.104.18.31 臺灣), 12/15/2020 09:52:24
推 alex391a: 我想想我應該想錯了 npc也是np hard 所以應該是只是跟講12/15 10:11
→ alex391a: 義常出現的那個np=npc=p12/15 10:11
→ alex391a: 所以其實題目應該跟 npc有p解 是等價的 可以討論看看12/15 10:14
→ mathtsai: a大畫的好像比較對 我那樣畫NP-H就不會是P了 12/15 13:44
→ mathtsai: 我的要把NP-H也加進P的範圍才行 12/15 13:45
所以，NP-H就算能在P時間內解出，也不代表它能在P時間內驗證答案嗎？
※ 編輯: seafoodccu (112.104.18.31 臺灣), 12/15/2020 14:22:24
→ mathtsai: 不確定耶 能在P時間解出卻不能被驗證 感覺也很怪 12/15 14:29
推 FRAXIS: 題目只是說有一個 NP-Hard 問題可以 P 時間解 12/17 11:18
→ FRAXIS: 不是說所有 NP-Hard 可以在 P 時間內解 12/17 11:19
→ FRAXIS: 所以就只能得到 P = NP = NP 12/17 11:20
→ FRAXIS: P = NP, 而且 P=NP 比 NPC 多兩個問題 12/17 11:22
→ mathtsai: 抱歉 沒看到只說一個 那就是只能得到P=NP 12/17 13:25