1. 先為reductions下較不嚴謹的定義, 我在reductions心得那篇的定義寫得較清楚
if A reduce to B with small time and so does B, A and B are equivalent,
i.e. there is the same complexity of A and B
2. NP-hard, NP-complete definition
X is NP-hard problem iff Y reduce to X with polynomial time,
for each Y belongs to NP.
X is NP-complete problem iff Y reduce to X with polynomial time,
for each Y belongs to NP and X is NP.
( this implys that NP-hard include NP-complete )
http://tbri.dorm8.nctu.edu.tw/~fcamel/upload/tmp/NP.gif
借放.....
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.20.39