[問題] 95台聯22題 有關NP-hard problem

[kkeve123 (在有太陽角落的香菇)]

如題 關於NP-hard problem

我找到的這個網站中的解釋

http://blog.xuite.net/jackie.xie/bluelove/7457574


NP-hard problem:

一個NP問題經由polynomial(time)演算法轉化(reduce)之後所成的問題。


請問這樣的定義在考試答題上可行?

因為我有看到其他的說法，可是好像怪怪的

http://kc-yang.blogspot.com/2010/03/np-hard-npcomplete.html


還是大家有看到更好的說法?


感激不盡!


最後補上一個很完整的整理(打文章時發現的)


http://www.csie.nctu.edu.tw/~chlo/web/docs/doc/data/algo/5.htm


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 163.25.118.79
推 laing20333:一個比在np中所有的問題還難的問題
推 FRAXIS:最後一個連結的說法是最精確的
→ FRAXIS:其他兩個只是很模糊的說明..
→ kkeve123:感謝~