https://i.imgur.com/B1IhQiS.jpg
想問一下這題，我的想法是所有NP問題因為都不難於NP-hard問題，所以都可以在p時間內
reduce到NP-hard
而題目說到NP-hard具P時間可解，那是否代表P=NP=NPC=NP-hard呢？還是僅有P=NP=NPC而
已？
謝謝！

我覺得是全部在同一個集合

NP-H可解->NP-C可解-> P = NPNP-C會包含在 P=NP 裡https://imgur.com/TS2MXBX 我覺得是這樣

Np hard 會在p 但因為定義不會在np(雖然這很怪）https://i.imgur.com/GRbdGsX.jpghttps://i.imgur.com/GRbdGsX.jpg全部問題都可以用p解決 但np hard不能用p驗證 所以 npc=np樓上那樣畫的話np hard就沒在p裡面了 我這樣理解應該沒有錯吧我想想我應該想錯了 npc也是np hard 所以應該是只是跟講義常出現的那個np=npc=p所以其實題目應該跟 npc有p解 是等價的 可以討論看看

a大畫的好像比較對 我那樣畫NP-H就不會是P了我的要把NP-H也加進P的範圍才行不確定耶 能在P時間解出卻不能被驗證 感覺也很怪

題目只是說有一個 NP-Hard 問題可以 P 時間解不是說所有 NP-Hard 可以在 P 時間內解所以就只能得到 P = NP = NPP = NP, 而且 P=NP 比 NPC 多兩個問題https://goo.gl/shLqO1

抱歉 沒看到只說一個 那就是只能得到P=NP