作者sugerplum (Faint)
看板NTUEE_Lab207
标题NP Hard and NP Complete
时间Thu Dec 24 11:27:04 2009
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