[資工] 不是NP 就是NP-Hard?

[harry2258 (陽光蜥蜴)]

我們說

一個問題如果是NP 也是NP-Hard 就是NPC

那如果一個問題不是NP

有沒有表示 這問題一定就是NP-Hard呢?

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.114.85.151
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1435250614.A.1E0.html
推 guida: 否 兩件事分開看 是不是NP-hard要另外去證明
推 FRAXIS: NP包含了所有比 NP-Hard 簡單的問題 (包含NP-hard）
→ FRAXIS: 如果問題不是 NP 代表這問題比 NP-Hard 難
→ FRAXIS: 所以不是 NP 的問題必定是 NP-Hard