107.txt

来自「This complete matlab for neural network」· 文本 代码 · 共 27 行

发信人: timeface (face), 信区: DataMining
标  题: Re: What the NP hard problem means?
发信站: 南京大学小百合站 (Wed Mar 27 11:24:29 2002), 站内信件

【 在 yaomc (白头翁&山东大汉) 的大作中提到: 】
: Some people like to say the NP hard or easy problems, what the means about 
: them, can anybody tell me ? thanks.

NP – Complexity class of a decision problem which answers can be checked by 
      an algorithm whose run time is polynomial in the size of the input.  

Doesn’t require or imply an answer can be found quickly, only that any 
claimed answer can be verified or refuted quickly

NP Complete-  Informally, a problem is NP-Complete if an answer can be 
verified quickly, and a quick algorithm to solve this problem can be 
used to solve all other NP problems quickly

NP-HARD: When a decision version of an optimization problem is proven to 
belong to the class of “NP – Complete” problems, an optimization version 
is NP-Hard.  Since there is no easy way to determine the optimal solution, 
an NP-Hard problem is at least as hard as, or harder than, any problem 
in NP

--
※ 来源:．南京大学小百合站 bbs.nju.edu.cn．[FROM: 202.38.79.104]