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